WARush

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

Codeforces #189 Div2 D "Psychos in a Line"

問題

http://codeforces.com/contest/320/problem/D

n人のサイコが一列に並んでいる。各サイコは一意な1~nのIDが割り当てられている。各ターンに、自分の右隣のサイコよりも大きいIDを持った各サイコは、右隣のサイコを殺す。殺すと同時に殺されるかサイコもいる可能性がある。

あなたは一列に並んだサイコに割り当てられたIDが与えられる。誰も殺せなくなるまで何ターンかかるかを計算せよ。

制約

1 <= n <= 10^5


ACしてるソースコードをカンニング

なんかスタックを使ってゴニョゴニョするらしい・・・
正直こんなコードは思いつかないし、なんでこれで合ってるかもちょっと良く分からない。


ソースコード

int main() {
    
    // 入力
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> id[i];
    }

    // 謎・・・
    stack< pair<int, int> > live;
    live.push( make_pair(id[n-1], 0) );

    int res = 0;
    for( int i = n - 2; i >= 0; i-- ){
        int op = 0;
        while( !live.empty() ){
            int lid = live.top().first;
            int lop = live.top().second;
            // 自分よりIDが大きければ自分を乗せて終了
            if( id[i] < lid ){
                break;
            }
            // 自分よりIDが小さければ潰して操作回数+1
            live.pop();
            op = max( op + 1, lop );
        }
        res = max( res, op );
        live.push( make_pair(id[i], op) );
    }

    cout << res << endl;
}