結果

問題 No.3198 Monotonic Query
コンテスト
ユーザー tanaka255
提出日時 2025-07-13 13:51:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 62 ms / 3,000 ms
コード長 1,315 bytes
コンパイル時間 3,634 ms
コンパイル使用メモリ 277,620 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-13 13:51:35
合計ジャッジ時間 6,472 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<class S,S(*op)(S,S),S(*e)()>
struct segtree{
  public:
    segtree(const vector<S>&v):_n((int)v.size()){
      log=ceil_pow2(_n);
      size=1<<log;
      d=vector<S>(2*size,e());
      rep(i,_n)d[size+i]=v[i];
      for(int i=size-1;1<=i;--i)update(i);
    }
    void set(int p,S x){
      p+=size;
      d[p]=x;
      for(int i=1;i<=log;++i)update(p>>i);
    }
    S get(int p){
      return d[p+size];
    }
    S prod(int l,int r){
      S sml=e(),smr=e();
      l+=size;
      r+=size;
      while(l<r){
        if(l&1)sml=op(sml,d[l++]);
        if(r&1)smr=op(d[--r],smr);
        l>>=1;
        r>>=1;
      }
      return op(sml,smr);
    }
  private:
    int _n,size,log;
    vector<S>d;
    void update(int k){
      d[k]=op(d[2*k],d[2*k+1]);
    }
    static int ceil_pow2(int n){
      int x=0;
      while((1<<x)<n)++x;
      return x;
    }
};
int op(int a,int b){
  return max(a,b);
}
constexpr int inf=1<<30;
int e(){
  return -inf;
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  int Q;cin>>Q;
  segtree<int,op,e>seg(vector<int>(2<<17,e()));
  int cur=0;
  while(Q--){
    int qt,x;cin>>qt>>x;
    if(qt==1){
      seg.set(cur++,x);
    }else{
      cout<<seg.prod(cur-x,cur)<<'\n';
    }
  }
}
0