結果
問題 | No.789 範囲の合計 |
ユーザー | 沙耶花 |
提出日時 | 2022-07-30 14:45:25 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 172 ms / 1,000 ms |
コード長 | 2,513 bytes |
コンパイル時間 | 4,066 ms |
コンパイル使用メモリ | 267,700 KB |
実行使用メモリ | 19,920 KB |
最終ジャッジ日時 | 2024-07-20 11:34:11 |
合計ジャッジ時間 | 7,105 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 155 ms
19,912 KB |
testcase_03 | AC | 81 ms
5,376 KB |
testcase_04 | AC | 172 ms
19,920 KB |
testcase_05 | AC | 143 ms
19,788 KB |
testcase_06 | AC | 157 ms
19,916 KB |
testcase_07 | AC | 82 ms
5,376 KB |
testcase_08 | AC | 149 ms
19,920 KB |
testcase_09 | AC | 141 ms
19,920 KB |
testcase_10 | AC | 142 ms
19,916 KB |
testcase_11 | AC | 132 ms
19,832 KB |
testcase_12 | AC | 134 ms
19,912 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 100000000000000000 template <class S, S (*op)(S, S), S (*e)()> struct dynamic_segtree { struct node{ int nxt[2]; S v; node(){ nxt[0] = -1; nxt[1] = -1; v = e(); } }; vector<node> nodes; dynamic_segtree() : dynamic_segtree(0) {} dynamic_segtree(long long n){ log = 0; while((1LL<<log) < n){ log++; } _n = n; nodes.resize(1,node()); } bool exists(int cur,int ind){ if(nodes[cur].nxt[ind]==-1){ return false; } return true; } int get_node(int cur,int ind){ if(nodes[cur].nxt[ind]==-1){ nodes[cur].nxt[ind] = nodes.size(); nodes.push_back(node()); } return nodes[cur].nxt[ind]; } void set(long long p, S x) { assert(0 <= p && p < _n); vector<int> t(1,0); for(int i=log-1;i>=0;i--){ t.push_back(get_node(t.back(),(p>>i)&1)); } reverse(t.begin(),t.end()); rep(i,t.size()){ if(i==0)nodes[t[i]].v = x; else{ update(t[i]); } } } S get(long long p) { assert(0 <= p && p < _n); int cur = 0; for(int i=log-1;i>=0;i--){ if(!exists(cur,(p>>i)&1))return e(); cur = get_node(cur,(p>>i)&1); } return nodes[cur].v; } S prod(long long l,long long r,int cur,int depth){ if(cur==-1||r-l==0)return e(); if(r-l==(1LL<<depth))return nodes[cur].v; r--; if((l>>(depth-1))&1){ l ^= 1LL<<(depth-1); r ^= 1LL<<(depth-1); return prod(l,r+1,nodes[cur].nxt[1],depth-1); } if(((r>>(depth-1))&1)==0){ return prod(l,r+1,nodes[cur].nxt[0],depth-1); } r ^= 1LL<<(depth-1); return op(prod(l,1LL<<(depth-1),nodes[cur].nxt[0],depth-1),prod(0,r+1,nodes[cur].nxt[1],depth-1)); } S prod(long long l, long long r) { assert(0 <= l && l <= r && r <= _n); return prod(l,r,0,log); } S all_prod() { return nodes[0].v; } void update(int k){ nodes[k].v = e(); rep(i,2){ if(nodes[k].nxt[i]==-1)continue; nodes[k].v = op(nodes[k].v,nodes[nodes[k].nxt[i]].v); } } long long _n,log,size; }; long long op(long long a,long long b){ return a+b; } long long e(){ return 0LL; } int main() { int n; cin>>n; dynamic_segtree<long long,op,e> seg(1000000005); long long ans = 0; rep(_,n){ int t,x,y; cin>>t>>x>>y; if(t==0){ seg.set(x,seg.get(x)+y); } else{ ans += seg.prod(x,y+1); } } cout<<ans<<endl; return 0; }