結果

問題 No.3198 Monotonic Query
コンテスト
ユーザー edon8618
提出日時 2025-07-11 21:46:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 248 ms / 3,000 ms
コード長 1,480 bytes
コンパイル時間 2,174 ms
コンパイル使用メモリ 195,768 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2025-07-12 10:53:22
合計ジャッジ時間 8,661 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep(i,r) for(ll i=0;i<(ll)r;i++)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)



// ll inf=(1ll<<62);

// ll rui(ll a,ll b){
//     if(b==0)return 1;
//     if(b%2==1) return a*rui(a*a,b/2);
//     return rui(a*a,b/2);
// }

// ll const mod=998244353ll;
// ll modrui(ll a,ll b){
//     if(b==0)return 1;
//     if(b%2==1) return a%mod*modrui(a%mod*a%mod,b/2)%mod;
//     return modrui(a%mod*a%mod,b/2)%mod;
// }

// ll inv(ll x){
//     return modrui(x,mod-2);
// }

ll len=2ll<<17,sz=0;
vl seg(len*2,0);


void update(ll p,ll x){
    p+=len;
    seg[p]=x;
    while(p>1){
        p/=2;
        seg[p]=max(seg[p*2],seg[p*2+1]);
    }
    sz++;
}

ll get_max(ll l,ll r,ll sl=0,ll sr=len,ll k=1){
    if(r <= sl || sr <= l)return 0;
    if(l <= sl && sr <= r)return seg[k];
    ll sm=(sl+sr)/2;
    ll lmax=get_max(l,r,sl,sm,k*2),rmax=get_max(l,r,sm,sr,k*2+1);
    return max(lmax,rmax);
}


void solve(){
    ll q,op,x;cin >> q;

    rep(i,q){
        cin >> op >> x;
        if(op==1){
            update(sz,x);
        }
        else{
            cout << get_max(sz-x,sz) << endl;
        }
    }
}



int main(){
    ll t=1;
    // cin >> t;
    while(t--)solve();
}
0