結果
問題 | No.789 範囲の合計 |
ユーザー | manjuuu_onsen |
提出日時 | 2021-09-14 01:13:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,495 bytes |
コンパイル時間 | 3,083 ms |
コンパイル使用メモリ | 191,488 KB |
実行使用メモリ | 45,816 KB |
最終ジャッジ日時 | 2024-06-26 03:02:54 |
合計ジャッジ時間 | 11,993 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 TLE * 1 |
ソースコード
#pragma GCC target("avx")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#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;unordered_map<int, T> data;T modify(int node) {if(data.count(node)) return data[node];else return 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)>>1;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;}