結果
問題 | No.789 範囲の合計 |
ユーザー | lorent_kyopro |
提出日時 | 2021-03-10 16:28:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 197 ms / 1,000 ms |
コード長 | 2,210 bytes |
コンパイル時間 | 2,051 ms |
コンパイル使用メモリ | 205,836 KB |
実行使用メモリ | 34,944 KB |
最終ジャッジ日時 | 2024-10-12 07:04:25 |
合計ジャッジ時間 | 4,554 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 178 ms
28,672 KB |
testcase_03 | AC | 79 ms
6,816 KB |
testcase_04 | AC | 197 ms
31,872 KB |
testcase_05 | AC | 159 ms
27,648 KB |
testcase_06 | AC | 158 ms
28,928 KB |
testcase_07 | AC | 73 ms
6,816 KB |
testcase_08 | AC | 165 ms
34,944 KB |
testcase_09 | AC | 151 ms
32,000 KB |
testcase_10 | AC | 163 ms
20,224 KB |
testcase_11 | AC | 145 ms
28,288 KB |
testcase_12 | AC | 145 ms
28,160 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,820 KB |
ソースコード
#include <bits/stdc++.h> template <class S, S (*op)(S, S), S (*e)()> class segtree { public: segtree(size_t n): n(n), root(nullptr) {} void set(size_t p, S x) { assert(p < n); root = set(root, 0, n, p, x); } S get(size_t p) { assert(p < n); return get(root, 0, n, p); } S prod(size_t l, size_t r) { assert(l <= r && r <= n); return prod(root, 0, n, l, r); } private: struct node { S value; node *left, *right; node(S value) : value(value), left(nullptr), right(nullptr) {} }; size_t n; node *root; node *set(node *t, size_t a, size_t b, size_t p, S x) { if (!t) t = new node(e()); if (b - a == 1) { t->value = x; return t; } size_t c = (a + b) >> 1; if (p < c) t->left = set(t->left, a, c, p, x); else t->right = set(t->right, c, b, p, x); t->value = op(t->left ? t->left->value : e(), t->right ? t->right->value : e()); return t; } S get(node *t, size_t a, size_t b, size_t p) { if (!t) return e(); if (b - a == 1) return t->value; size_t c = (a + b) >> 1; if (p < c) return get(t->left, a, c, p); else return get(t->right, c, b, p); } S prod(node *t, size_t a, size_t b, size_t l, size_t r) { if (!t) return e(); if (b <= l || r <= a) return e(); if (l <= a && b <= r) return t->value; size_t c = (a + b) >> 1; S resl = prod(t->left, a, c, l, r); S resr = prod(t->right, c, b, l, r); return op(resl, resr); } }; using S = int; S op(S a, S b) { return a + b; } S e() { return 0; } int main() { const size_t n = 1000000001; segtree<S, op, e> seg(n); size_t q; std::cin >> q; long long ans = 0; while (q--) { int type; std::cin >> type; if (type == 0) { size_t x; int y; std::cin >> x >> y; seg.set(x, seg.get(x) + y); } else { size_t l, r; std::cin >> l >> r; ans += seg.prod(l, r + 1); } } std::cout << ans << '\n'; }