WARush

SRMの結果とか、解けた問題のコードを書いていきます

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さんの記事を参考にして解いた。

イメージ図
f:id:Ekaing:20130307202034j:plain

各地形がどのラダーに属するかを持っておけば、
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;
        }
    }
}