WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。地形の高さを表すA(1),A(2)....A(n-1),A(n)というN個の整数が与えられる。Rの二つの整数を含むクエリがM個与えられる。クエリは地形のL地点からR地点まで、つまりA(L),A(L+1)....A(R-1),A(R)の部分が"Ladder"であるかを問い合わせている。A(R)となるかどうかである。文句なしにLadder1,3,4,5,6,7,8これもLadder(X==R)5,5,4,4,3,2,1これまたLadder(X==L)3,4,6,7,6,7,4これはLadderじゃない各クエリの区間が"Ladder"であれば"Yes"そうでなければ"No"を表示しなさい。N考えた事(WA)各クエリごとに地形を走査してLadderを判定してたんじゃ計算量はO(NM)となってダメ。次の変わり目はどこかを地形全部で最初に計算しちゃう。クエリのLが下り坂部分だったら次の変わり目までにRがあればよい。クエリのLが上り坂部分だったら次の次の変わり目までにRがあればよい。下ってたら下り坂としちゃってて間違えだった。torus711さんの記事を参考にして解いた。各地形がどのラダーに属するかを持っておけば、LとRが同じラダーにあるかどうかを判定すればよく、O(1)でクエリに答えられる。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。