結果

問題 No.3198 Monotonic Query
コンテスト
ユーザー jiangxinyang
提出日時 2025-07-11 21:36:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 254 ms / 3,000 ms
コード長 1,065 bytes
コンパイル時間 1,944 ms
コンパイル使用メモリ 195,500 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-12 10:52:19
合計ジャッジ時間 7,854 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;

int main() {
    int q;
    cin >> q;
    int n = 1;
    while (n < q) n <<= 1;
    vector<int> seg(2 * n, numeric_limits<int>::min());
    int sz = 0;
    auto update = [&](int pos, int v) {
        pos += n;
        seg[pos] = v;
        for (pos >>= 1; pos > 0; pos >>= 1) seg[pos] = max(seg[pos << 1], seg[(pos << 1) | 1]);
    };
    auto query = [&](int l, int r) {
        int res = numeric_limits<int>::min();
        l += n, r += n;
        while (l <= r) {
            if (l & 1) res = max(res, seg[l++]);
            if (!(r & 1)) res = max(res, seg[r--]);
            l >>= 1;
            r >>= 1;
        }
        return res;
    };
    for (int i = 0; i < q; i++) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            update(sz, x);
            sz++;
        } else {
            int l = sz - x, r = sz - 1;
            cout << query(l, r) << "\n";
        }
    }
    return 0;
}
0