結果
問題 | No.789 範囲の合計 |
ユーザー | toma |
提出日時 | 2019-09-09 01:30:25 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 805 ms / 1,000 ms |
コード長 | 1,720 bytes |
コンパイル時間 | 2,772 ms |
コンパイル使用メモリ | 191,228 KB |
実行使用メモリ | 45,644 KB |
最終ジャッジ日時 | 2023-09-09 22:53:35 |
合計ジャッジ時間 | 10,378 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 759 ms
42,136 KB |
testcase_03 | AC | 223 ms
4,376 KB |
testcase_04 | AC | 805 ms
42,744 KB |
testcase_05 | AC | 643 ms
42,020 KB |
testcase_06 | AC | 686 ms
42,080 KB |
testcase_07 | AC | 397 ms
4,376 KB |
testcase_08 | AC | 724 ms
45,644 KB |
testcase_09 | AC | 660 ms
42,764 KB |
testcase_10 | AC | 540 ms
25,296 KB |
testcase_11 | AC | 498 ms
42,260 KB |
testcase_12 | AC | 499 ms
42,128 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,376 KB |
ソースコード
#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include"bits/stdc++.h" using namespace std; #define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++) #define rep(i,n) REP((i),0,(n)) using ll = long long; constexpr ll n = 1ll << 30; // 横幅 template<typename T> class DynamicSegmentTree { private: //using F = function<T(T, T)>; // モノイド型 //const F f; // モノイド const T e; // モノイド単位元 unordered_map<int, T> data; // 存在しないindexではeを返します T at(int idx) { return data.find(idx) == data.end() ? e : data[idx]; } public: // init忘れに注意 DynamicSegmentTree(T e) :e(e) {} void add_val(int idx, T val) { idx += n - 1; if (data.find(idx) == data.end())data[idx] = 0; data[idx] += val; while (idx > 0) { idx = (idx - 1) / 2; data[idx] = (data.find(2 * idx + 1) == data.end() ? e : data[2 * idx + 1]) + (data.find(2 * idx + 2) == data.end() ? e : data[2 * idx + 2]); } } T query(int a, int b, int k = 0, int l = 0, int r = n) { if (r <= a || b <= l)return e; if (a <= l && r <= b) { return data.find(k) == data.end() ? e : data[k]; } else { T vl = data.find(2 * k + 1) == data.end() ? e : query(a, b, 2 * k + 1, l, (l + r) / 2); T vr = data.find(2 * k + 2) == data.end() ? e : query(a, b, 2 * k + 2, (l + r) / 2, r); //return f(vl, vr); return vl + vr; } } }; int main() { int n; cin >> n; //function<ll(ll, ll)> f = [](ll a, ll b) {return a + b; }; DynamicSegmentTree<ll> dst(0); ll res = 0; while (n--) { int com, x, y; cin >> com >> x >> y; if (com == 0) { dst.add_val(x, y); } else { res += dst.query(x, y + 1); } } cout << res << endl; return 0; }