結果

問題 No.3116 More and more teleporter
コンテスト
ユーザー Tatsu_mr
提出日時 2025-04-27 17:41:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 79 ms / 2,000 ms
コード長 4,136 bytes
コンパイル時間 3,254 ms
コンパイル使用メモリ 279,636 KB
実行使用メモリ 11,380 KB
最終ジャッジ日時 2025-04-27 17:41:58
合計ジャッジ時間 6,165 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
#define SZ(v) ((int)(v).size())

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

struct SetupIo {
    SetupIo() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} setupio;

template <class S, S (*op)(S, S), S (*e)()>
struct SegmentTree {
    private:
    int n, sz, lg;
    vector<S> d;

    void build() {
        while (sz < n) {
            sz *= 2, lg++;
        }
        d.resize(sz * 2, e());
    }

    void update(int k) {
        d[k] = op(d[k << 1], d[k << 1 | 1]);
    }

    public:
    SegmentTree() {}
    SegmentTree(int n_) : n(n_), sz(1), lg(0) { build(); }
    SegmentTree(vector<S> &a) : n(a.size()), sz(1), lg(0) {
        build();
        for (int i = 0; i < n; i++) { d[i + sz] = a[i]; }
        for (int i = sz - 1; i >= 1; i--) { update(i); }
    }

    void set(int p, S x) {
        assert(0 <= p && p < n);
        p += sz;
        d[p] = x;
        for (int i = 1; i <= lg; i++) {
            update(p >> i);
        }
    }

    S get(int p) const {
        assert(0 <= p && p < n);
        return d[p + sz];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        S sml = e(), smr = e();
        l += sz, r += sz;
        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() const { return d[1]; }

    template <bool (*f)(S)>
    int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F>
    int max_right(int l, F f) const {
        assert(0 <= l && l <= n);
        assert(f(e()));
        if (l == n) { return n; }
        l += sz;
        S sm = e();
        do {
            while (l % 2 == 0) { l >>= 1; }
            if (!f(op(sm, d[l]))) {
                while (l < sz) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - sz;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= n);
        assert(f(e()));
        if (r == 0) { return 0; }
        r += sz;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) { r >>= 1; }
            if (!f(op(d[r], sm))) {
                while (r < sz) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - sz;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
};

lint op(lint a, lint b) { return min(a, b); }
lint e() { return LINF; }

int main() {
    int n, q;
    cin >> n >> q;
    SegmentTree<lint, op, e> l(n), r(n);
    rep(_, q) {
        int t;
        cin >> t;
        if (t == 1) {
            lint x;
            cin >> x;
            x--;
            lint ans1 = x;
            lint ans2 = l.prod(0, x + 1) + x;
            lint ans3 = r.prod(x, n) - x;
            cout << min({ans1, ans2, ans3}) << "\n";
        } else {
            lint x, c;
            cin >> x >> c;
            x--;
            if (c - x < l.get(x)) {
                l.set(x, c - x);
            }
            if (c + x < r.get(x)) {
                r.set(x, c + x);
            }
        }
    }
}
0