結果
問題 |
No.3198 Monotonic Query
|
ユーザー |
|
提出日時 | 2025-07-11 21:32:56 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 270 ms / 3,000 ms |
コード長 | 2,739 bytes |
コンパイル時間 | 3,110 ms |
コンパイル使用メモリ | 278,820 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-07-12 10:51:32 |
合計ジャッジ時間 | 9,831 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> #define fi first #define se second #define rep(i,s,n) for (int i = (s); i < (n); ++i) #define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define len(x) (int)(x).size() #define dup(x,y) (((x)+(y)-1)/(y)) #define pb push_back #define eb emplace_back #define Field(T) vector<vector<T>> using namespace std; using ll = long long; using ull = unsigned long long; template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>; using P = pair<int,int>; template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;} template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;} template<class S, S (*op)(S, S), S (*e)()> struct SegTree { public: SegTree() : SegTree(0) {} SegTree(int n) : SegTree(vector<S>(n, e())) {} SegTree(int n, S v) : SegTree(vector<S>(n, v)) {} SegTree(const vector<S>& v) : _n(int(v.size())){ lg = 0; while ((1U << lg) < (unsigned int)(_n)) lg++; siz = 1 << lg; d = vector<S>(2 * siz, e()); for (int i = 0; i < _n; ++i) d[siz + i] = v[i]; for (int i = siz-1; i >= 1; --i) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += siz; d[p] = x; for (int i = 1; i <= lg; ++i) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p+siz]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += siz; r += siz; 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); } S all_prod() { return d[1]; } using F = function<bool(S)>; // max_{r \in [l, n]} f(prod(l, r)) == true int max_right(int l, const F &f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += siz; S v = e(); do { while(l % 2 == 0) l >>= 1; if (!f(op(v, d[l]))) { while(l < siz) { l *= 2; if (f(op(v, d[l]))) { v = op(v, d[l]); ++l; } } return l - siz; } v = op(v, d[l]); ++l; } while((l & -l) != l); return _n; } private: int _n, siz, lg; vector<S> d; void update(int k) {d[k] = op(d[2*k], d[2*k+1]);} }; using S = int; S op(S a, S b) { return max(a, b); } S e() {return 0;} int main() { int q; cin >> q; SegTree<int,op,e> seg(q); int idx = 0; while(q--) { int t; cin >> t; if (t == 1) { int x; cin >> x; seg.set(idx, x); ++idx; } else { int k; cin >> k; cout << seg.prod(idx-k, idx) << endl; } } return 0; }