結果

問題 No.789 範囲の合計
ユーザー 沙耶花沙耶花
提出日時 2022-07-30 14:45:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 161 ms / 1,000 ms
コード長 2,513 bytes
コンパイル時間 4,480 ms
コンパイル使用メモリ 266,140 KB
実行使用メモリ 21,220 KB
最終ジャッジ日時 2023-09-27 17:14:48
合計ジャッジ時間 8,079 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 155 ms
20,544 KB
testcase_03 AC 84 ms
4,380 KB
testcase_04 AC 161 ms
20,008 KB
testcase_05 AC 145 ms
20,000 KB
testcase_06 AC 145 ms
20,308 KB
testcase_07 AC 83 ms
4,380 KB
testcase_08 AC 145 ms
20,176 KB
testcase_09 AC 135 ms
21,220 KB
testcase_10 AC 145 ms
19,872 KB
testcase_11 AC 131 ms
20,228 KB
testcase_12 AC 133 ms
20,052 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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