結果

問題 No.789 範囲の合計
ユーザー manjuuu_onsenmanjuuu_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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0