結果
| 問題 | No.3198 Monotonic Query |
| コンテスト | |
| ユーザー |
 joji
|
| 提出日時 | 2026-01-22 12:15:25 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 93 ms / 3,000 ms |
| コード長 | 6,543 bytes |
| 記録 | |
| コンパイル時間 | 3,538 ms |
| コンパイル使用メモリ | 343,772 KB |
| 実行使用メモリ | 7,852 KB |
| 最終ジャッジ日時 | 2026-01-22 12:15:34 |
| 合計ジャッジ時間 | 8,280 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
#line 1 "3198.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3198"
#line 2 "ds/segtree/segtree.hpp"
#include <algorithm>
#include <cassert>
#include <vector>
template <typename Monoid> struct SegTree {
using T = typename Monoid::value_type;
int n;
std::vector<T> t;
SegTree() : n(0) {}
SegTree(int n) : n(n) { t.resize(4 * n, Monoid::e()); }
SegTree(const std::vector<T> &A) : n((int)A.size()) {
t.resize(4 * n, Monoid::e());
build(A, 1, 0, n - 1);
}
void build(const std::vector<T> &A, int v, int tl, int tr) {
if (tl == tr) {
t[v] = A[tl];
} else {
int tm = (tl + tr) / 2;
build(A, v * 2, tl, tm);
build(A, v * 2 + 1, tm + 1, tr);
t[v] = Monoid::op(t[v * 2], t[v * 2 + 1]);
}
}
void update(int v, int tl, int tr, int pos, const T &new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(v * 2, tl, tm, pos, new_val);
} else {
update(v * 2 + 1, tm + 1, tr, pos, new_val);
}
t[v] = Monoid::op(t[v * 2], t[v * 2 + 1]);
}
}
void update(int pos, const T &new_val) { update(1, 0, n - 1, pos, new_val); }
T query(int v, int tl, int tr, int l, int r) const {
if (l > r) {
return Monoid::e();
}
if (l == tl && r == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return Monoid::op(query(v * 2, tl, tm, l, std::min(r, tm)),
query(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r));
}
T query(int l, int r) const { return query(1, 0, n - 1, l, r); }
T get(int pos) const { return query(pos, pos); }
template <class Pred> int max_right(int l, Pred pred) const {
assert(0 <= l && l <= n);
assert(pred(Monoid::e()));
T acc = Monoid::e();
return max_right_dfs(1, 0, n - 1, l, pred, acc);
}
template <class Pred> int max_right_dfs(int v, int tl, int tr, int l, Pred pred, T &acc) const {
if (tr < l) return l;
if (tl >= l) {
T nxt = Monoid::op(acc, t[v]);
if (pred(nxt)) {
acc = nxt;
return tr + 1;
}
if (tl == tr) return tl;
}
int tm = (tl + tr) / 2;
int res = max_right_dfs(v * 2, tl, tm, l, pred, acc);
if (res <= tm) return res;
return max_right_dfs(v * 2 + 1, tm + 1, tr, l, pred, acc);
}
template <class Pred> int min_left(int r, Pred pred) const {
assert(0 <= r && r <= n);
assert(pred(Monoid::e()));
T acc = Monoid::e();
int res = min_left_dfs(1, 0, n - 1, r, pred, acc);
return res < 0 ? 0 : res;
}
template <class Pred> int min_left_dfs(int v, int tl, int tr, int r, Pred pred, T &acc) const {
if (tl >= r) return r;
if (tr < r) {
T nxt = Monoid::op(t[v], acc);
if (pred(nxt)) {
acc = nxt;
return tl - 1;
}
if (tl == tr) return tl + 1;
}
int tm = (tl + tr) / 2;
int res = min_left_dfs(v * 2 + 1, tm + 1, tr, r, pred, acc);
if (res >= tm + 1) return res;
return min_left_dfs(v * 2, tl, tm, r, pred, acc);
}
template <class Pred> int find_first(int l, int r, Pred check) const {
assert(0 <= l && l <= r && r < n);
return find_first_dfs(1, 0, n - 1, l, r, check);
}
template <class Pred> int find_first_dfs(int v, int tl, int tr, int l, int r, Pred check) const {
if (l > r || !check(t[v])) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int res = find_first_dfs(v * 2, tl, tm, l, std::min(r, tm), check);
if (res != -1) return res;
return find_first_dfs(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, check);
}
template <class Pred> int find_last(int l, int r, Pred check) const {
assert(0 <= l && l <= r && r < n);
return find_last_dfs(1, 0, n - 1, l, r, check);
}
template <class Pred> int find_last_dfs(int v, int tl, int tr, int l, int r, Pred check) const {
if (l > r || !check(t[v])) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int res = find_last_dfs(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, check);
if (res != -1) return res;
return find_last_dfs(v * 2, tl, tm, l, std::min(r, tm), check);
}
};
#line 3 "3198.test.cpp"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 30, MAXN = 200005;
void solve() {
int active = 0;
int Q;
cin >> Q;
struct Monoid {
using value_type = int;
static int e() { return -INF; }
static int op(const int &a, const int &b) { return max(a, b); }
};
SegTree<Monoid> seg(MAXN);
while (Q--) {
int t;
cin >> t;
if (t == 1) {
int x;
cin >> x;
seg.update(active, x);
active++;
} else {
int k;
cin >> k;
cout << seg.query(active - k, active) << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}