#451436 (C++14) No.789 範囲の合計

• 問題: No.789 範囲の合計
• ユーザー: chocorusk
• 提出日時: 2020-03-30 09:38:06
• 言語: C++14 (gcc 12.3.0 + boost 1.83.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	151 ms; 31,616 KB
testcase_03	AC	50 ms; 5,376 KB
testcase_04	AC	163 ms; 35,072 KB
testcase_05	AC	129 ms; 30,208 KB
testcase_06	AC	133 ms; 31,488 KB
testcase_07	AC	43 ms; 5,376 KB
testcase_08	AC	143 ms; 38,272 KB
testcase_09	AC	131 ms; 34,944 KB
testcase_10	AC	120 ms; 22,016 KB
testcase_11	AC	100 ms; 31,360 KB
testcase_12	AC	100 ms; 31,360 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB

ソースコード

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