結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; } }