結果
問題 | No.789 範囲の合計 |
ユーザー |
![]() |
提出日時 | 2019-02-08 21:35:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 464 ms / 1,000 ms |
コード長 | 2,036 bytes |
コンパイル時間 | 2,555 ms |
コンパイル使用メモリ | 212,920 KB |
最終ジャッジ日時 | 2025-01-06 20:54:04 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#include<bits/stdc++.h>using namespace std;using Int = long long;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}struct FastIO{FastIO(){cin.tie(0);ios::sync_with_stdio(0);}}fastio_beet;template<typename T>vector<T> compress(vector<T> v){sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());return v;}template<typename T>map<T, Int> dict(const vector<T> &v){map<T, Int> res;for(Int i=0;i<(Int)v.size();i++)res[v[i]]=i;return res;}template<typename T>struct BIT{Int n;vector<T> bit;//1-indexedBIT():n(-1){}BIT(Int n_,T d):n(n_),bit(n_+1,d){}T sum(Int i){T s=bit[0];for(Int x=i;x>0;x-=(x&-x))s+=bit[x];return s;}void add(Int i,T a){if(i==0) return;for(Int x=i;x<=n;x+=(x&-x))bit[x]+=a;}Int lower_bound(Int w){if(w<=0) return 0;Int x=0,r=1;while(r<n) r<<=1;for(Int k=r;k>0;k>>=1){if(x+k<=n&&bit[x+k]<w){w-=bit[x+k];x+=k;}}return x+1;}T sum0(Int i){return sum(i+1);}void add0(Int i,T a){add(i+1,a);}T query(Int l,Int r){return sum(r-1)-sum(l-1);}T query0(Int l,Int r){return sum(r)-sum(l);}};//INSERT ABOVE HEREsigned main(){Int q;cin>>q;vector<Int> ts(q),xs(q),ys(q);for(Int i=0;i<q;i++) cin>>ts[i]>>xs[i]>>ys[i];vector<Int> vs;vs.emplace_back(-1);vs.emplace_back(1e9+1);for(Int i=0;i<q;i++){vs.emplace_back(xs[i]-1);vs.emplace_back(xs[i]);vs.emplace_back(xs[i]+1);vs.emplace_back(ys[i]-1);vs.emplace_back(ys[i]);vs.emplace_back(ys[i]+1);}vs=compress(vs);auto mv=dict(vs);BIT<Int> bit(mv.size(),0);Int ans=0;for(Int i=0;i<q;i++){if(ts[i]==0){bit.add(mv[xs[i]],ys[i]);}if(ts[i]==1){ans+=bit.query(mv[xs[i]],mv[ys[i]+1]);}}cout<<ans<<endl;return 0;}