結果

問題 No.3061 Cut and Maximums
ユーザー tute7627
提出日時 2024-07-07 15:13:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 353 ms / 2,000 ms
コード長 1,431 bytes
コンパイル時間 2,489 ms
コンパイル使用メモリ 209,652 KB
実行使用メモリ 47,172 KB
最終ジャッジ日時 2025-03-14 19:58:14
合計ジャッジ時間 13,421 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

int main(){
    int N; cin>>N;
    vector<int> P(N);
    assert(2 <= N && N <= 300000);
    set<int> pst;
    for(int i = 0; i < N; i++){
        cin >> P[i];
        assert(1 <= P[i] && P[i] <= N);
        pst.insert(P[i]);
        P[i]--;
    }
    assert(pst.size() == N);
    string S; cin >> S;
    assert(S.size() == N);
    for(auto c : S) assert(c == 'W' || c == 'B');
    
    if(S[N - 1] == 'W' && S != string(N, 'W')){
        cout << -1 << endl;
        return 0;
    }
    else if(S[N - 1] == 'W'){
        cout << 0 << endl;
        return 0;
    }

    for(int i = 0; i < N; i++){
        if(P[i] == N - 1){
            rotate(P.begin(), P.begin() + i, P.end());
            P.erase(P.begin());
            break;
        }
    }

    vector<int>l(N, -1), r(N, -1);
    stack<int> st;
    for(int i = 0; i < N; i++){
        while(!st.empty() && P[st.top()] < P[i]){
            l[i] = st.top();
            st.pop();
        }
        if(!st.empty()) r[st.top()] = i;
        st.push(i);
    }
    auto dfs = [&](auto dfs, int pos) -> int {
        int lv = l[pos] == -1 ? 0 : dfs(dfs, l[pos]);
        int rv = r[pos] == -1 ? 0 : dfs(dfs, r[pos]);
        if(S[P[pos]] == 'W'){
            return lv + rv;
        }
        else{
            return max({lv, rv, 1});
        }
    };
    cout << max(1, dfs(dfs, max_element(P.begin(), P.end()) - P.begin())) << endl;
}
0