結果

問題 No.3238 Shadow
ユーザー t98slider
提出日時 2025-08-15 23:14:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,586 bytes
コンパイル時間 3,538 ms
コンパイル使用メモリ 255,660 KB
実行使用メモリ 9,388 KB
最終ジャッジ日時 2025-08-15 23:15:06
合計ジャッジ時間 5,978 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;

int op(int lhs, int rhs){return min(lhs, rhs);}
constexpr int e(){return 1 << 30;}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    vector<int> pos(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].second;
        a[i].first = i + 1;
        pos[a[i].second - 1] = i;
    }
    vector<bool> used(n);
    atcoder::segtree<int, op, e> seg(n + 1);
    auto check = [&](int p){
        if(used[p]) return true;
        auto [x, y] = a[p];
        int v = seg.prod(0, x);
        return v >= y;
    };
    vector<int> S;
    auto ope = [&](int p, bool add){
        auto [x, y] = a[p];
        if(add){
            if(used[p]) return;
            seg.set(x, y);
            S.emplace_back(p);
            used[p] = true;
        }else{
            seg.set(x, e());
        }
    };
    for(int rx = 0, ry = 0; rx < n && ry < n; ){
        bool flg = true;
        while(flg){
            flg = false;
            while(rx < n && check(rx)){
                ope(rx++, true);
                flg = true;
            }
            while(ry < n && check(pos[ry])){
                ope(pos[ry++], true);
                flg = true;
            }
        }
        int xmn = 1 << 30, ymn = 1 << 30;
        for(auto p : S){
            auto [x, y] = a[p];
            ope(p, false);
            xmn = min(xmn, x);
            ymn = min(ymn, y);
        }
        S.clear();
        cout << xmn << ' ' << ymn << '\n';
    }
}
0