結果
問題 | No.789 範囲の合計 |
ユーザー | nok0 |
提出日時 | 2021-03-12 17:50:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 73 ms / 1,000 ms |
コード長 | 2,333 bytes |
コンパイル時間 | 2,485 ms |
コンパイル使用メモリ | 220,768 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-14 06:17:59 |
合計ジャッジ時間 | 3,846 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 71 ms
6,816 KB |
testcase_03 | AC | 52 ms
6,816 KB |
testcase_04 | AC | 73 ms
6,816 KB |
testcase_05 | AC | 55 ms
6,816 KB |
testcase_06 | AC | 59 ms
6,816 KB |
testcase_07 | AC | 39 ms
6,820 KB |
testcase_08 | AC | 54 ms
6,824 KB |
testcase_09 | AC | 50 ms
6,816 KB |
testcase_10 | AC | 67 ms
6,820 KB |
testcase_11 | AC | 43 ms
6,816 KB |
testcase_12 | AC | 45 ms
6,824 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 2 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h> template <class S, S (*op)(S, S), S (*e)()> struct dynamic_segtree { private: struct node; using node_ptr = std::unique_ptr<node>; struct node { int index; S value, product; node_ptr lef, rig; node(int index, S value) : index(index), value(value), product(value), lef(nullptr), rig(nullptr) {} }; const int n; node_ptr root; S value(const node_ptr& t) const { return t == nullptr ? e() : t->product; } node_ptr& set(node_ptr& t, const int a, const int b, int p, S x) const { if(t == nullptr) return t = std::make_unique<node>(p, x); if(t->index == p) { t->value = x; t->product = op(value(t->lef), op(t->value, value(t->rig))); return t; } int c = (a + b) >> 1; if(p < c) { if(t->index < p) std::swap(t->index, p), std::swap(t->value, x); t->lef = std::move(set(t->lef, a, c, p, x)); } else { if(p < t->index) std::swap(p, t->index), std::swap(x, t->value); t->rig = std::move(set(t->rig, c, b, p, x)); } t->product = op(value(t->lef), op(t->value, value(t->rig))); return t; } S get(const node_ptr& t, const int a, const int b, int p) const { if(t == nullptr) return e(); if(t->index == p) return t->value; int c = (a + b) >> 1; if(p < c) return get(t->lef, a, c, p); else return get(t->rig, c, b, p); } S prod(const node_ptr& t, const int a, const int b, int l, int r) const { if(t == nullptr or b <= l or r <= a) return e(); if(l <= a and b <= r) return t->product; int c = (a + b) >> 1; S res = prod(t->lef, a, c, l, r); if(l <= t->index and t->index < r) res = op(res, t->value); return op(res, prod(t->rig, c, b, l, r)); } public: dynamic_segtree(int n) : n(n), root(nullptr) {} void set(int p, S x) { assert(0 <= p and p < n); root = std::move(set(root, 0, n, p, x)); } S get(int p) { assert(0 <= p and p < n); return get(root, 0, n, p); } S prod(int l, int r) { assert(l <= r and r <= n); return prod(root, 0, n, l, r); } }; using S = int; S op(S x, S y) { return x + y; } S e() { return 0; } const int sz = 1e9 + 1; int n, t, x, y; long long res; int main() { dynamic_segtree<S, op, e> seg(sz); scanf("%d", &n); while(n--) { scanf("%d%d%d", &t, &x, &y); if(t == 0) seg.set(x, seg.get(x) + y); else res += seg.prod(x, y + 1); } printf("%lld\n", res); return 0; }