結果
問題 | No.789 範囲の合計 |
ユーザー | だれ |
提出日時 | 2023-11-17 17:53:08 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 122 ms / 1,000 ms |
コード長 | 2,565 bytes |
コンパイル時間 | 1,097 ms |
コンパイル使用メモリ | 80,396 KB |
実行使用メモリ | 6,656 KB |
最終ジャッジ日時 | 2024-09-26 05:29:42 |
合計ジャッジ時間 | 3,659 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 121 ms
6,016 KB |
testcase_03 | AC | 76 ms
5,376 KB |
testcase_04 | AC | 122 ms
6,272 KB |
testcase_05 | AC | 105 ms
5,760 KB |
testcase_06 | AC | 111 ms
5,888 KB |
testcase_07 | AC | 64 ms
5,376 KB |
testcase_08 | AC | 97 ms
6,656 KB |
testcase_09 | AC | 96 ms
6,272 KB |
testcase_10 | AC | 122 ms
5,376 KB |
testcase_11 | AC | 93 ms
6,144 KB |
testcase_12 | AC | 95 ms
6,272 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
ソースコード
#include <algorithm> #include <iostream> #include <new> #include <utility> #include <vector> template <class T, T op(T, T), T e()> struct DynamicSegTree { using i64 = long long; struct node { node *left, *right; T prod; T val; i64 pos; node(int p, T x) : left(nullptr), right(nullptr), prod(x), val(x), pos(p) {} void update() { prod = op(op((left ? left->prod : e()), val), (right ? right->prod : e())); } }; node* root; i64 n; DynamicSegTree(i64 _n) : n(_n), root(nullptr) {} void _set(node*& t, i64 p, T& x, i64 l, i64 r) { if (!t) { t = new node(p, x); return; } if (t->pos == p) { t->val = x; } else { i64 mid = (l + r) >> 1; if (p < mid) { if (t->pos < p) { std::swap(t->pos, p); std::swap(t->val, x); } _set(t->left, p, x, l, mid); } else { if (t->pos > p) { std::swap(t->pos, p); std::swap(t->val, x); } _set(t->right, p, x, mid, r); } } t->update(); return; } T _get(node*& t, i64 p, i64 l, i64 r) { if (!t) return e(); if (t->pos == p) return t->val; i64 mid = (l + r) >> 1; if (p < mid) return _get(t->left, p, l, mid); else return _get(t->right, p, mid, r); } T _prod(node*& t, i64 L, i64 R, i64 l, i64 r) { if (!t || R <= l || r <= L) return e(); if (L <= l && r <= R) return t->prod; i64 mid = (l + r) >> 1; T res = _prod(t->left, L, R, l, mid); if (L <= t->pos && t->pos < R) res = op(res, t->val); return op(res, _prod(t->right, L, R, mid, r)); } void set(i64 p, T x) { _set(root, p, x, 0, n); } T get(i64 p) { return _get(root, p, 0, n); } T prod(i64 l, i64 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(1e9 + 1000); 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"; }