結果

問題 No.3198 Monotonic Query
ユーザー umimel
提出日時 2025-07-11 21:46:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 361 ms / 3,000 ms
コード長 2,202 bytes
コンパイル時間 2,512 ms
コンパイル使用メモリ 172,336 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2025-07-12 10:53:26
合計ジャッジ時間 10,328 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;


template<typename T, T (*op)(T, T), T (*e)()>
struct segtree{
    int n;
    vector<T> dat;

    segtree(int n_){
        n = 1;
        while(n < n_) n*=2;
        dat.resize(2*n, e());
    }

    void update(int k, T x){
        k += n-1;
        dat[k] = x;
        while(k > 0){
            k = (k-1)/2;
            dat[k] = op(dat[2*k+1], dat[2*k+2]);
        }
    }

    // the prod element of [a, b)
    T query(int a, int b){return query_sub(a, b, 0, 0, n);}

    T query_sub(int a, int b, int k, int l, int r){
        if(r <= a || b <= l){
            return e();
        }else if(a <= l && r <= b){
            return dat[k];
        }else{
            T vl = query_sub(a, b, 2*k+1, l, (l+r)/2);
            T vr = query_sub(a, b, 2*k+2, (l+r)/2, r);
            return op(vl, vr);
        }
    }
};


int op1(int a, int b){
    return a+b;
}
int e1(){
    return 0;
}
pair<int, int> op2(pair<int, int> a, pair<int, int> b){
    return max(a, b);
}
pair<int, int> e2(){
    return {0, -1};
}

void solve(){
    int q; cin >> q;
    segtree<int, op1, e1> cnt(q);
    segtree<pair<int, int>, op2, e2> mx(q);
    for(int i=0; i<q; i++){
        int type; cin >> type;
        if(type == 1){
            int x; cin >> x;
            cnt.update(i, 1);
            mx.update(i, {x, i});
        }
        if(type == 2){
            int k; cin >> k;
            int lo = 0, hi = i, mid;
            while(hi-lo>1){
                mid = (lo + hi) / 2;
                if(k <= cnt.query(mid, i)) lo = mid;
                else hi= mid;
            }
            cout << mx.query(lo, i).first << "\n";
        }
    }

}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T=1;
    //cin >> T;
    while(T--) solve();
}
0