結果
問題 |
No.3116 More and more teleporter
|
ユーザー |
|
提出日時 | 2025-04-16 01:20:56 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 2,143 bytes |
コンパイル時間 | 3,812 ms |
コンパイル使用メモリ | 279,100 KB |
実行使用メモリ | 12,804 KB |
最終ジャッジ日時 | 2025-04-16 01:21:11 |
合計ジャッジ時間 | 6,717 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; template<typename S, S (*op)(S, S), S (*e)()> class SegmentTree { private: int _n, sz; vector<S> data; void calc(int k) { data[k] = op(data[k << 1], data[k << 1 | 1]); } public: SegmentTree() = default; explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())) {} explicit SegmentTree(const vector<S>& v) : _n(v.size()) { sz = 1; while(sz < _n) sz <<= 1; data.assign(sz << 1, e()); for(int i = 0; i < _n; i++) data[sz + i] = v[i]; for(int i = sz - 1; i >= 1; i--) calc(i); } void set(int p, S x) { assert(0 <= p && p < _n); p += sz; data[p] = x; while(p >>= 1) calc(p); } S get(int p) { assert(0 <= p && p < _n); return data[p + sz]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sl = e(), sr = e(); l += sz; r += sz; while(l < r) { if(l & 1) sl = op(sl, data[l++]); if(r & 1) sr = op(data[--r], sr); l >>= 1; r >>= 1; } return op(sl, sr); } S all_prod() { return data[1]; } }; // c - i + x と c + i - x を計算したい // xはクエリのタイミングで固定なので // min c-i (i<x) // min c+i (x<=i) // の二つを管理する const ll inf = 1e18; ll op(ll a, ll b) { return min(a, b); } ll e() { return inf; } int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, q; cin >> n >> q; SegmentTree<ll, op, e> seg1(n), seg2(n); seg1.set(0, 0); seg2.set(0, 0); while(q--) { int t; cin >> t; if(t == 1){ ll x; cin >> x; x--; ll ans = min(seg1.prod(0, x) + x, seg2.prod(x, n) - x); cout << ans << endl; }else{ ll x, c; cin >> x >> c; x--; if(c - x < seg1.get(x)) { seg1.set(x, c - x); } if(c + x < seg2.get(x)) { seg2.set(x, c + x); } } } }