結果
問題 | No.789 範囲の合計 |
ユーザー | Kyo_s_s |
提出日時 | 2023-07-09 01:50:19 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 166 ms / 1,000 ms |
コード長 | 3,499 bytes |
コンパイル時間 | 3,243 ms |
コンパイル使用メモリ | 206,716 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-07-22 22:10:16 |
合計ジャッジ時間 | 5,277 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 159 ms
5,888 KB |
testcase_03 | AC | 99 ms
5,376 KB |
testcase_04 | AC | 166 ms
6,272 KB |
testcase_05 | AC | 143 ms
5,760 KB |
testcase_06 | AC | 147 ms
5,888 KB |
testcase_07 | AC | 73 ms
5,376 KB |
testcase_08 | AC | 138 ms
6,528 KB |
testcase_09 | AC | 131 ms
6,272 KB |
testcase_10 | AC | 154 ms
5,376 KB |
testcase_11 | AC | 127 ms
6,272 KB |
testcase_12 | AC | 125 ms
6,272 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<class M> class DynamicSegtree { public: using S = typename M::T; DynamicSegtree() : DynamicSegtree(LONG_LONG_MAX / 2) {} DynamicSegtree(long long limit) : limit(limit), root(nullptr) {} void set(long long p, S x) { set(root, 0, limit, p, x); } S get(long long p) const { return get(root, 0, limit, p); } S prod(long long l, long long r) const { assert(l <= r); return prod(root, 0, limit, l, r); } S all_prod() const { return root ? root->product : M::e(); } void reset(long long l, long long r) { assert(l <= r); return reset(root, 0, limit, l, r); } private: struct node; using node_ptr = std::unique_ptr<node>; struct node { long long index; S value, product; node_ptr left, right; node(long long index, S value) : index(index), value(value), product(value), left(nullptr), right(nullptr) {} void update() { product = M::op(M::op(left ? left->product : M::e(), value), right ? right->product : M::e()); } }; long long limit = LONG_LONG_MAX / 2; node_ptr root; void set(node_ptr& t, long long a, long long b, long long p, S x) const { if (!t) { t = std::make_unique<node>(p, x); return; } if (t->index == p) { t->value = x; t->update(); return; } long long c = (a + b) >> 1; if (p < c) { if (t->index < p) std::swap(t->index, p), std::swap(t->value, x); set(t->left, a, c, p, x); } else { if (p < t->index) std::swap(p, t->index), std::swap(x, t->value); set(t->right, c, b, p, x); } t->update(); } S get(const node_ptr& t, long long a, long long b, long long p) const { if (!t) return M::e(); if (t->index == p) return t->value; long long c = (a + b) >> 1; if (p < c) return get(t->left, a, c, p); else return get(t->right, c, b, p); } S prod(const node_ptr& t, long long a, long long b, long long l, long long r) const { if (!t || b <= l || r <= a) return M::e(); if (l <= a && b <= r) return t->product; long long c = (a + b) >> 1; S result = prod(t->left, a, c, l, r); if (l <= t->index && t->index < r) result = M::op(result, t->value); return M::op(result, prod(t->right, c, b, l, r)); } void reset(node_ptr& t, long long a, long long b, long long l, long long r) const { if (!t || b <= l || r <= a) return; if (l <= a && b <= r) { t.reset(); return; } long long c = (a + b) >> 1; reset(t->left, a, c, l, r); reset(t->right, c, b, l, r); t->update(); } }; struct Monoid { using T = long long; static T op(T a, T b) { return a + b; } static T e() { return 0; } }; int main() { DynamicSegtree<Monoid> seg; int N; cin >> N; long long ans = 0; while (N--) { int t; cin >> t; if (t == 0) { long long x, y; cin >> x >> y; seg.set(x, seg.get(x) + y); } else { long long l, r; cin >> l >> r; ans += seg.prod(l, r + 1); } } cout << ans << endl; }