結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
|
提出日時 | 2025-07-11 22:52:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 246 ms / 3,000 ms |
コード長 | 1,308 bytes |
コンパイル時間 | 757 ms |
コンパイル使用メモリ | 80,496 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-07-12 10:55:49 |
合計ジャッジ時間 | 6,854 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; using ll = long long; using P = pair<int, int>; struct segtree{ int N, iden; vector<int> tree; int pow2(int n){ int ans=1; while(ans<n) ans*=2; return ans; } void build(vector<int> &a, int n){ N=pow2(n); iden=-1; tree.resize(2*N, iden); for(int i=0; i<n; i++) tree[N+i]=a[i]; for(int i=N-1; i>=1; i--) tree[i]=max(tree[2*i], tree[2*i+1]); } void update(int node, int x){ //0-indexed int i=node+N; tree[i]=max(tree[i], x); i/=2; while(i>0){ tree[i]=max(tree[2*i], tree[2*i+1]); i/=2; } return; } int query(int s, int t){ //0-indexed int left=s+N, right=t+N; int ans=iden; while(left<=right){ if(left%2==1){ ans=max(ans, tree[left]); left++; } if(right%2==0){ ans=max(ans, tree[right]); right--; } left/=2, right/=2; } return ans; } }; int main(){ int q; cin >> q; vector<int> a(q, -1); segtree seg; seg.build(a, q); int len=0; while(q--){ int t; cin >> t; if(t==1){ int x; cin >> x; seg.update(len, x); len++; } else{ int k; cin >> k; cout << seg.query(len-k, len-1) << '\n'; } } return 0; }