結果
問題 | No.789 範囲の合計 |
ユーザー | manjuuu_onsen |
提出日時 | 2021-09-14 01:08:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,411 bytes |
コンパイル時間 | 1,919 ms |
コンパイル使用メモリ | 175,888 KB |
実行使用メモリ | 97,024 KB |
最終ジャッジ日時 | 2024-06-26 02:57:36 |
合計ジャッジ時間 | 4,970 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 TLE * 1 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using pint = pair<int,int>;template<class M> class SegmentTree { public: using T = typename M::value_type;private:int m, n;map<int, T> data;T modify(int node) {if(data.count(node)) return data[node];else return (data[node] = M::id());}T rec(int l, int r, int node, int node_l, int node_r) {if(node_r <= l || node_l >= r)return M::id();if(node_l >= l && node_r <= r)return modify(node);int mid = (node_l + node_r) / 2;return M::op( rec(l, r, node * 2, node_l, mid), rec(l, r, node * 2 + 1, mid, node_r) );}public:SegmentTree() = default;SegmentTree(int N) {m = N;for(n = 1; n < N; n <<= 1);}T prod(int l, int r) {return rec(l, r, 1, 0, n);}T get (int i){ return modify(i + n); }T all_prod() {return modify(1);}void set(int index, T val) {index += n;data[index] = val;while(index != 1){index >>= 1;data[index] = M::op( modify(index<<1), modify((index<<1) + 1));}}};template<class T> class RSQ { public: using value_type = T;static T op(T l, T r){ return l + r; }static T id(){return 0;}};int main() {int Q; cin >> Q;SegmentTree<RSQ<ll>> seg(1'000'000'001);ll ans = 0;for(int i = 0; i < Q; i++) {int t, a, b; cin >> t >> a >> b;if(t == 0) seg.set(a, seg.get(a) + b);else {ans += seg.prod(a, b + 1);}}cout << ans << endl;}