結果

問題 No.3198 Monotonic Query
ユーザー alcea
提出日時 2025-07-11 21:31:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 243 ms / 3,000 ms
コード長 820 bytes
コンパイル時間 1,924 ms
コンパイル使用メモリ 196,016 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-07-12 10:51:12
合計ジャッジ時間 8,317 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;
template<typename T,T (*op)(T,T),T (*e)()>
struct SegmentTree{
public:
  SegmentTree(int _n):n(_n),li(0),v(_n<<1,e()){}
  T prod(int l,int r){
    resolve();
    l+=n;r+=n;
    T lret=e(),rret=e();
    while(l<r){
      if(l&1) lret=op(lret,v[l++]);
      if(r&1) rret=op(v[--r],rret);
      l>>=1;r>>=1;
    }
    return op(lret,rret);
  }
  T &operator[](int i){
    resolve();
    return v[li=i+n];
  }
private:
  int n,li;
  vector<T> v;
  void resolve(){for(;li>>=1;) v[li]=op(v[li<<1],v[li<<1|1]);}
};
int op(int x,int y){return max(x,y);}
int e(){return 0;}
int main(){
  int q;
  cin>>q;
  SegmentTree<int,op,e> seg(q);
  int idx=0;
  for(int i=0;i<q;i++){
    int op,a;
    cin>>op>>a;
    if(op==1) seg[idx++]=a;
    if(op==2) cout<<seg.prod(idx-a,idx)<<endl;
  }
}
0