結果
問題 |
No.3116 More and more teleporter
|
ユーザー |
![]() |
提出日時 | 2025-04-20 17:59:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 2,159 bytes |
コンパイル時間 | 2,255 ms |
コンパイル使用メモリ | 201,676 KB |
実行使用メモリ | 14,272 KB |
最終ジャッジ日時 | 2025-04-20 17:59:29 |
合計ジャッジ時間 | 5,051 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (ll)4e18; struct SegTree { int n; vector<ll> st; SegTree(int _n) : n(_n), st(4 * n, INF) {} void update(int p, ll v) { update(1, 1, n, p, v); } void update(int node, int l, int r, int p, ll v) { if (l == r) { st[node] = min(st[node], v); return; } int m = (l + r) >> 1; if (p <= m) update(node << 1, l, m, p, v); else update(node << 1 | 1, m + 1, r, p, v); st[node] = min(st[node << 1], st[node << 1 | 1]); } // 区間 [L,R] の最小値 ll query(int L, int R) { return query(1, 1, n, L, R); } ll query(int node, int l, int r, int L, int R) { if (r < L || R < l) return INF; if (L <= l && r <= R) return st[node]; int m = (l + r) >> 1; return min( query(node << 1, l, m, L, R), query(node << 1 | 1, m + 1, r, L, R)); } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; SegTree segL(N), segR(N); // segL: i にテレポーター設置時に c - i を更新 // segR: i にテレポーター設置時に c + i を更新 while (Q--) { int t; cin >> t; if (t == 1) { int x; cin >> x; // 全歩行 ll ans = x - 1; // 左側テレポーターを使って右へ歩く if (x >= 1) { ll a = segL.query(1, x); ans = min(ans, a + x); } // 右側テレポーターを使って左へ歩く if (x <= N) { ll b = segR.query(x, N); ans = min(ans, b - x); } cout << ans << "\n"; } else { int x; ll c; cin >> x >> c; // 位置 x にテレポーター設置 segL.update(x, c - x); segR.update(x, c + x); } } return 0; }