Codeforces #171 Div2 C "Ladder"
問題
地形の高さを表すA(1),A(2)....A(n-1),A(n)というN個の整数が与えられる。
またL Rの二つの整数を含むクエリがM個与えられる。
クエリは地形のL地点からR地点まで、つまりA(L),A(L+1)....A(R-1),A(R)の部分が
"Ladder"であるかを問い合わせている。
LからRが"Ladder"であるとは、L <= X <= Rとして、
A(L) <= A(L+1) <= A(L+2)....<= A(X) >= A(X+1).... A(R-1) >= A(R)
となるかどうかである。
つまりLからRでへこんだ部分がなければいいよってこと
例) 1,3,5,6,4,3,2 文句なしにLadder 1,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"を表示しなさい。
制約
1 <= N,M <= 10^5
1 <= A(i) <= 10^9
1 <= L,R <= N
考えた事(WA)
各クエリごとに地形を走査してLadderを判定してたんじゃ
計算量はO(NM)となってダメ。
i番目の位置は上り坂か下り坂か、
次の変わり目はどこかを地形全部で最初に計算しちゃう。
クエリのLが下り坂部分だったら次の変わり目までにRがあればよい。
クエリのLが上り坂部分だったら次の次の変わり目までにRがあればよい。
事後
平坦な部分をその前まで上ってたら上り坂
下ってたら下り坂としちゃってて間違えだった。
またもやtorus711さんの記事を参考にして解いた。
イメージ図
各地形がどのラダーに属するかを持っておけば、
LとRが同じラダーにあるかどうかを判定すればよく、
O(1)でクエリに答えられる。
ソースコード
const int MAX_N = 100000; int N, M; int arr[MAX_N+2]; // 地形 int ladderNum[MAX_N+1][2]; // 地形iのラダー番号 int main() { // ifstream in( "data.txt" ); istream& in = cin; in >> N >> M; for( int i = 1; i <= N; i++ ){ in >> arr[i]; } arr[N+1] = 2000000000; // ラダー番号を記憶させる memset( ladderNum, -1, sizeof(ladderNum) ); int lNum = 0; int s = 1; bool doDown = false; for( int i = 1; i <= N; i++ ){ if( arr[i] > arr[i+1] ) doDown = true; if( arr[i] < arr[i+1] ){ if( doDown || i == N ){ for( int j = s; j <= i; j++ ){ int k = 0; if( ladderNum[j][k] != -1 ) k = 1; ladderNum[j][k] = lNum; } lNum++; if( i == N ) break; for( ; i >= 1; i-- ){ if( arr[i] < arr[i-1] ) break; } doDown = false; s = i; } } } // クエリに答える for( int i = 0; i < M; i++ ){ int L, R; in >> L >> R; if( ladderNum[L][0] == ladderNum[R][0] ){ cout << "Yes" << endl; }else if( ladderNum[L][1] == ladderNum[R][0] ){ cout << "Yes" << endl; }else{ cout << "No" << endl; } } }