結果
問題 | No.789 範囲の合計 |
ユーザー | mugen_1337 |
提出日時 | 2020-07-01 19:19:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 191 ms / 1,000 ms |
コード長 | 2,170 bytes |
コンパイル時間 | 2,632 ms |
コンパイル使用メモリ | 221,156 KB |
実行使用メモリ | 14,964 KB |
最終ジャッジ日時 | 2024-09-14 02:27:11 |
合計ジャッジ時間 | 5,477 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 173 ms
13,940 KB |
testcase_03 | AC | 45 ms
5,620 KB |
testcase_04 | AC | 164 ms
13,564 KB |
testcase_05 | AC | 130 ms
14,072 KB |
testcase_06 | AC | 138 ms
13,944 KB |
testcase_07 | AC | 36 ms
5,492 KB |
testcase_08 | AC | 93 ms
9,080 KB |
testcase_09 | AC | 83 ms
8,312 KB |
testcase_10 | AC | 191 ms
14,964 KB |
testcase_11 | AC | 138 ms
13,560 KB |
testcase_12 | AC | 144 ms
13,688 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define INF 1000000000 #define mod 1000000007 using ll=long long; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} template<typename Monoid> struct SegmentTree{ using F=function<Monoid(Monoid,Monoid)>; int sz; vector<Monoid> seg; const F f; const Monoid gen; SegmentTree(int n,const F f,const Monoid &gen):f(f),gen(gen){ sz=1; while(sz<n)sz<<=1; seg.assign(2*sz,gen); } void set(int k,const Monoid &x){ seg[k+sz]=x; } void build(){ for(int k=sz-1;k>0;k--) seg[k]=f(seg[2*k],seg[2*k+1]); } void update(int k,const Monoid &x){ k+=sz; seg[k]=x; while(k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]); } // [a,b) Monoid query(int a,int b){ Monoid L=gen,R=gen; for(a+=sz,b+=sz;a<b;a>>=1,b>>=1){ if(a&1) L=f(L,seg[a++]); if(b&1) R=f(seg[--b],R); } return f(L,R); } Monoid operator[](const int &k)const { return seg[k+sz]; } }; int f(int a,int b){ return a+b; } signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n;cin>>n; map<int,int> id; vector<tuple<int,int,int>> qs(n); vector<int> v; rep(i,n){ int t,x,y;cin>>t>>x>>y; qs[i]=make_tuple(t,x,y); if(t==0) v.push_back(x); else{ v.push_back(x);v.push_back(y); } } sort(ALL(v)); v.erase(unique(ALL(v)),v.end()); rep(i,v.size())id[v[i]]=i; SegmentTree<int> seg(id.size(),f,0); ll ans=0; rep(i,n){ int t,x,y; tie(t,x,y)=qs[i]; if(t==0) seg.update(id[x],seg[id[x]]+y); else ans+=seg.query(id[x],id[y]+1); } cout<<ans<<endl; return 0; }