結果
問題 | No.789 範囲の合計 |
ユーザー | だれ |
提出日時 | 2023-11-18 01:07:20 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 166 ms / 1,000 ms |
コード長 | 3,152 bytes |
コンパイル時間 | 1,158 ms |
コンパイル使用メモリ | 101,960 KB |
実行使用メモリ | 35,192 KB |
最終ジャッジ日時 | 2024-09-26 05:36:47 |
合計ジャッジ時間 | 3,692 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
34,976 KB |
testcase_01 | AC | 12 ms
35,072 KB |
testcase_02 | AC | 166 ms
35,072 KB |
testcase_03 | AC | 113 ms
35,076 KB |
testcase_04 | AC | 161 ms
35,072 KB |
testcase_05 | AC | 145 ms
35,072 KB |
testcase_06 | AC | 147 ms
35,072 KB |
testcase_07 | AC | 100 ms
35,072 KB |
testcase_08 | AC | 137 ms
35,096 KB |
testcase_09 | AC | 133 ms
35,036 KB |
testcase_10 | AC | 162 ms
35,072 KB |
testcase_11 | AC | 126 ms
34,944 KB |
testcase_12 | AC | 127 ms
35,192 KB |
testcase_13 | AC | 12 ms
34,984 KB |
testcase_14 | AC | 12 ms
35,004 KB |
ソースコード
#include <algorithm> #include <iostream> #include <new> #include <utility> #include <vector> const int MAX_SIZE = 1010101; 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 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); } }; template <class T, T op(T, T), T e()> DynamicSegTree<T, op, e>::node DynamicSegTree<T, op, e>::pool[MAX_SIZE]; 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; i64 n = 1e9; n += 100; DynamicSegTree<i64, op, e> seg(n); DynamicSegTree<i64, op, e> seg2(n); i64 ans = 0; i64 debug = 0; i64 q_max = q; while (q--) { int t; i64 l, r; cin >> t >> l >> r; if (t == 0) { seg.set(l, seg.get(l) + r); seg2.set(q, 1); } else { ans += seg.prod(l, r + 1); debug += seg2.prod(0, q_max + 1); } } cout << ans << "\n"; cerr << debug << "\n"; }