結果

問題 No.3116 More and more teleporter
ユーザー issaimaru
提出日時 2025-04-20 12:10:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,299 bytes
コンパイル時間 2,658 ms
コンパイル使用メモリ 201,816 KB
実行使用メモリ 14,092 KB
最終ジャッジ日時 2025-04-20 12:10:17
合計ジャッジ時間 4,262 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

const ll INF = 1LL << 60;

struct SegmentTree {
    int n;
    vector<pair<ll, ll>> tree;

    SegmentTree(int _n) : n(_n), tree(4 * _n, {INF, INF}) {}

    void update(int idx, ll val, int node = 1, int start = 1, int end = -1) {
        if (end == -1) end = n;
        if (start == end) {
            tree[node] = {val + start, val - start};
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid)
            update(idx, val, node * 2, start, mid);
        else
            update(idx, val, node * 2 + 1, mid + 1, end);
        tree[node] = {min(tree[node * 2].first, tree[node * 2 + 1].first),
                      min(tree[node * 2].second, tree[node * 2 + 1].second)};
    }

    pair<ll, ll> query(int left, int right, int node = 1, int start = 1, int end = -1) {
        if (end == -1) end = n;
        if (left > end || right < start || left > right) return {INF, INF};
        if (left <= start && end <= right) return tree[node];
        int mid = (start + end) / 2;
        pair<ll, ll> left_res = {INF, INF}, right_res = {INF, INF};
        if (left <= mid)
            left_res = query(left, right, node * 2, start, mid);
        if (right > mid)
            right_res = query(left, right, node * 2 + 1, mid + 1, end);
        return {min(left_res.first, right_res.first),
                min(left_res.second, right_res.second)};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;
    SegmentTree seg_tree(N);

    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            ll min_cost = x - 1;
            if (x > 1) {
                auto res = seg_tree.query(1, x - 1);
                if (res.second != INF) {
                    min_cost = min(min_cost, res.second + x);
                }
            }

            auto res = seg_tree.query(x, N);
            if (res.first != INF) {
                min_cost = min(min_cost, res.first - x);
            }
            cout << min_cost << '\n';
        } else {
            int x, c;
            cin >> x >> c;
            seg_tree.update(x, c);
        }
    }
    return 0;
}
0