結果
問題 | No.789 範囲の合計 |
ユーザー | だれ |
提出日時 | 2023-11-18 01:44:38 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 126 ms / 1,000 ms |
コード長 | 2,844 bytes |
コンパイル時間 | 1,087 ms |
コンパイル使用メモリ | 99,148 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-26 05:37:26 |
合計ジャッジ時間 | 3,223 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,812 KB |
testcase_01 | AC | 4 ms
6,944 KB |
testcase_02 | AC | 118 ms
6,940 KB |
testcase_03 | AC | 79 ms
6,940 KB |
testcase_04 | AC | 117 ms
6,944 KB |
testcase_05 | AC | 102 ms
6,940 KB |
testcase_06 | AC | 105 ms
6,940 KB |
testcase_07 | AC | 70 ms
6,944 KB |
testcase_08 | AC | 92 ms
6,940 KB |
testcase_09 | AC | 88 ms
6,944 KB |
testcase_10 | AC | 126 ms
6,944 KB |
testcase_11 | AC | 90 ms
6,944 KB |
testcase_12 | AC | 94 ms
6,944 KB |
testcase_13 | AC | 3 ms
6,944 KB |
testcase_14 | AC | 4 ms
6,944 KB |
ソースコード
#include <algorithm> #include <iostream> #include <new> #include <utility> #include <vector> const int MAX_SIZE = 101010; template <class T, T op(T, T), T e()> struct DynamicSegTree { using u64 = unsigned long long; struct node { int left, right; T prod; T val; u64 pos; node() : node(-1, e()) {} node(int p, T x) : left(0), right(0), prod(x), val(x), pos(p) {} }; inline u64 index(int x) { return pool[x].pos; } static inline int counter = 1; u64 n; int root; static inline node pool[MAX_SIZE]; DynamicSegTree(u64 _n) : n(_n), root(0) {} void update(int t) { pool[t].prod = op(op(pool[pool[t].left].prod, pool[t].val), pool[pool[t].right].prod); } void _set(int& t, u64 p, T& x, u64 l, u64 r) { if (!t) { t = counter++; pool[t] = node(p, x); return; } if (index(t) == p) { pool[t].val = x; } else { u64 mid = (l + r) >> 1; if (p < mid) { if (index(t) < p) { std::swap(pool[t].pos, p); std::swap(pool[t].val, x); } _set(pool[t].left, p, x, l, mid); } else { if (index(t) > p) { std::swap(pool[t].pos, p); std::swap(pool[t].val, x); } _set(pool[t].right, p, x, mid, r); } } update(t); return; } T _get(int& t, u64 p, u64 l, u64 r) { if (!t) return e(); if (index(t) == p) return pool[t].val; u64 mid = (l + r) >> 1; if (p < mid) return _get(pool[t].left, p, l, mid); else return _get(pool[t].right, p, mid, r); } T _prod(int& t, u64 L, u64 R, u64 l, u64 r) { if (!t || R <= l || r <= L) return e(); if (L <= l && r <= R) return pool[t].prod; u64 mid = (l + r) >> 1; T res = _prod(pool[t].left, L, R, l, mid); if (L <= index(t) && index(t) < R) res = op(res, pool[t].val); return op(res, _prod(pool[t].right, L, R, mid, r)); } void set(u64 p, T x) { _set(root, p, x, 0, n); } T get(u64 p) { return _get(root, p, 0, n); } T prod(u64 l, u64 r) { return _prod(root, l, r, 0, n); } }; using namespace std; using i64 = long long; i64 op(i64 a, i64 b) { return a + b; } i64 e() { return 0; } int main() { int q; cin >> q; DynamicSegTree<i64, op, e> seg(1'000'000'001); i64 ans = 0; while (q--) { int t; i64 l, r; cin >> t >> l >> r; if (t == 0) seg.set(l, seg.get(l) + r); else { ans += seg.prod(l, r + 1); } } cout << ans << "\n"; }