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