結果

問題 No.789 範囲の合計
ユーザー chocorusk
提出日時 2020-03-30 09:38:06
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 163 ms / 1,000 ms
コード長 1,912 bytes
コンパイル時間 1,165 ms
コンパイル使用メモリ 122,824 KB
実行使用メモリ 38,272 KB
最終ジャッジ日時 2024-06-11 07:38:06
合計ジャッジ時間 3,922 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<typename T, typename Monoid, T kmn, T kmx>
struct SegmentTreeDynamic{
	using F=function<Monoid(Monoid, Monoid)>;
	const F f;
	const Monoid e;
	struct Node{
		Monoid x;
		Node *l, *r;
		Node(Monoid x):x(x), l(nullptr), r(nullptr){}
	};
	Node *root;
	SegmentTreeDynamic(const F f, const Monoid &e):f(f), e(e), root(nullptr){}
	Node *update(Node *t, T k, const Monoid &x, T l, T r){
		if(!t) t=new Node(e);
		if(r-l==1){
			t->x=x;
			return t;
		}
		T m=(l+r)/2;
		if(k<m) t->l=update(t->l, k, x, l, m);
		else t->r=update(t->r, k, x, m, r);
		t->x=f((t->l)?(t->l->x):e, (t->r)?(t->r->x):e);
		return t;
	}
	void update(T k, const Monoid &x){
		root=update(root, k, x, kmn, kmx);
	}
	Monoid query(Node *t, T a, T b, T l, T r){
		if(b<=l || r<=a) return e;
		if(!t) return e;
		if(a<=l && r<=b) return t->x;
		T m=(l+r)/2;
		return f(query(t->l, a, b, l, m), query(t->r, a, b, m, r));
	}
	Monoid query(T l, T r){
		return query(root, l, r, kmn, kmx);
	}
};

int main()
{
	int n;
	scanf("%d", &n);
	SegmentTreeDynamic<int, int, 0, 1000000001> seg([](int x, int y){ return x+y;}, 0);
	map<int, int> a;
	ll ans=0;
	while(n--){
		int t;
		scanf("%d", &t);
		if(t==0){
			int x, y;
			scanf("%d %d", &x, &y);
			a[x]+=y;
			seg.update(x, a[x]);
		}else{
			int l, r;
			scanf("%d %d", &l, &r);
			r++;
			ans+=seg.query(l, r);
		}
	}
	printf("%lld\n", ans);
	return 0;
}
0