結果

問題 No.1827 最長部分スーパーリッチ門松列列
ユーザー srjywrdnprkt
提出日時 2025-03-29 01:54:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 1,161 bytes
コンパイル時間 3,308 ms
コンパイル使用メモリ 278,300 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-29 01:54:10
合計ジャッジ時間 7,366 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

void solve(){

    int N, p, s=1, mx=0;
    cin >> N;
    vector<int> rev(N);
    vector<bool> sign(N, 1);
    for (int i=0; i<N; i++){
        cin >> p; p--;
        rev[p] = i;
    }
    for (int i=0; i<N; i++){
        sign[rev[i]] = 0;
        if (rev[i]){
            if (sign[rev[i]-1]) s++;
            else s--;
        }
        if (rev[i] != N-1){
            if (sign[rev[i]+1]) s++;
            else s--;
        }
        mx = max(mx, s);
    }
    cout << mx << '\n';
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       iを境界にして、i以下のものを下側(-)、それ以外を上側(+)に採用する。
       -と+の連結成分の数の最大値が答え。これはiの小さい方から差分計算できる。
       1 4 3 2 5
       + + + + + -> 1
       - + + + + -> 2
       - + + - + -> 4
       - + - - + -> 4
       - - - - + -> 2
       - - - - - -> 1
    */

    int T;
    cin >> T;
    while(T--) solve();

    return 0;
}
0