結果
問題 | No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに |
ユーザー |
|
提出日時 | 2022-10-15 00:42:14 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 696 ms / 6,000 ms |
コード長 | 1,189 bytes |
コンパイル時間 | 1,127 ms |
コンパイル使用メモリ | 89,748 KB |
実行使用メモリ | 27,920 KB |
最終ジャッジ日時 | 2024-06-23 10:44:20 |
合計ジャッジ時間 | 30,588 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<queue> #include<atcoder/segtree> using namespace std; long op(long a,long b){return a+b;} long e(){return 0L;} int N,Q; int A[2<<17],T[2<<17],L[2<<17],R[2<<17]; long ans[2<<17]; int main() { cin>>N; vector<pair<int,int> >AT(N); for(int i=0;i<N;i++) { cin>>A[i]>>T[i]; AT[i]=make_pair(T[i],i); } sort(AT.begin(),AT.end()); cin>>Q; vector<pair<int,int> >LR(Q); for(int i=0;i<Q;i++) { int D; cin>>D>>L[i]>>R[i]; L[i]--; LR[i]=make_pair(D,i); } sort(LR.begin(),LR.end()); atcoder::segtree<long,op,e>prv(vector<long>(A,A+N)),cur(N),cnt(N); priority_queue<pair<int,int> >queue; int ati=0; for(pair<int,int>q:LR) { while(ati<N&&AT[ati].first<=q.first) { int id=AT[ati].second; prv.set(id,0); cur.set(id,A[id]+T[id]-1); cnt.set(id,1); queue.push(make_pair(-(A[id]+T[id]-1),id)); ati++; } while(!queue.empty()&&-queue.top().first<=q.first) { int id=queue.top().second; cur.set(id,0); cnt.set(id,0); queue.pop(); } int l=L[q.second],r=R[q.second]; ans[q.second]=prv.prod(l,r)+cur.prod(l,r)-cnt.prod(l,r)*q.first; } for(int i=0;i<Q;i++)cout<<ans[i]<<"\n"; }