結果
問題 | No.789 範囲の合計 |
ユーザー | wk1080id |
提出日時 | 2019-05-11 19:04:34 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 196 ms / 1,000 ms |
コード長 | 2,598 bytes |
コンパイル時間 | 989 ms |
コンパイル使用メモリ | 91,460 KB |
実行使用メモリ | 16,384 KB |
最終ジャッジ日時 | 2024-07-02 01:16:42 |
合計ジャッジ時間 | 3,608 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 174 ms
16,380 KB |
testcase_03 | AC | 93 ms
9,724 KB |
testcase_04 | AC | 167 ms
16,120 KB |
testcase_05 | AC | 150 ms
16,384 KB |
testcase_06 | AC | 156 ms
16,252 KB |
testcase_07 | AC | 81 ms
9,724 KB |
testcase_08 | AC | 123 ms
12,024 KB |
testcase_09 | AC | 117 ms
9,852 KB |
testcase_10 | AC | 196 ms
16,384 KB |
testcase_11 | AC | 161 ms
16,124 KB |
testcase_12 | AC | 158 ms
16,248 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
ソースコード
#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cctype> #include<math.h> #include<string> #include<string.h> #include<stack> #include<queue> #include<vector> #include<utility> #include<set> #include<map> #include<stdlib.h> #include<iomanip> using namespace std; #define ll long long #define ld long double #define EPS 0.0000000001 #define INF 1e9 #define LINF (ll)INF*INF #define MOD 1000000007 #define rep(i,n) for(int i=0;i<(n);i++) #define loop(i,a,n) for(int i=a;i<(n);i++) #define all(in) in.begin(),in.end() #define shosu(x) fixed<<setprecision(x) #define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! typedef vector<int> vi; typedef vector<string> vs; typedef pair<int,int> pii; typedef vector<pii> vp; int gcd(int a, int b){ if(b==0) return a; return gcd(b,a%b); } int lcm(int a, int b){ return a/gcd(a,b)*b; } class SegTree{ private: int n; vector<int> seg; int init = 0; //初期化の値(単位元) int combine(int a, int b){ return a+b; } public: SegTree (){} SegTree(int size){ n=1; while(n<size)n<<=1; seg=vector<int>(2*n,init); } SegTree(const vector<int> &in){ n=1; while(n<in.size())n<<=1; seg=vector<int>(2*n,init); for(int i=n-1+in.size()-1;i>=0;i--){ if(n-1<=i)seg[i]=in[i-(n-1)]; else seg[i]=combine(seg[i*2+1],seg[i*2+2]); } } //k-th(0-indexd) を a void update(int k,int a){ k+=n-1; seg[k] += a; while(k>0){ k=(k-1)/2; seg[k]=combine(seg[k*2+1],seg[k*2+2]); } } //[a,b)について調べる int query(int a,int b,int k=0,int l=0,int r=-1){ if(r==-1)r=n; if(r<=a || b<=l)return init; if(a<=l &&r<=b)return seg[k]; int vl=query(a,b,k*2+1,l,(l+r)/2); int vr=query(a,b,k*2+2,(l+r)/2,r); return combine(vl,vr); } }; void compress(vi &v){ sort(all(v)); v.erase(unique(all(v)),v.end()); } int idx(int i,vector<int> &c){ return lower_bound(c.begin(),c.end(),i)-c.begin(); } signed main(void) { int n; cin >> n; vi qa(n),qb(n),qc(n); vi x; rep(i,n){ cin >> qa[i] >> qb[i] >> qc[i]; x.push_back(qb[i]); x.push_back(qb[i]+1); if(qa[i]){ x.push_back(qc[i]); x.push_back(qc[i]+1); } } compress(x); SegTree st(x.size()); int ans = 0; rep(i,n){ if(qa[i]){ ans += st.query(idx(qb[i],x),idx(qc[i]+1,x)); }else{ st.update(idx(qb[i],x), qc[i]); } } cout << ans << endl; }