結果
問題 |
No.2101 [Cherry Alpha N] ずっとこの数列だったらいいのに
|
ユーザー |
![]() |
提出日時 | 2022-10-12 23:54:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,199 ms / 6,000 ms |
コード長 | 1,927 bytes |
コンパイル時間 | 2,638 ms |
コンパイル使用メモリ | 216,008 KB |
最終ジャッジ日時 | 2025-02-08 02:20:28 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long struct SegmentTree { private: int n; vector<int> node; public: SegmentTree(vector<int> v) { int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, 0); for(int i=0; i<sz; i++) node[i+n-1] = v[i]; for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2]; } void add(int k, int val) { k += (n - 1); node[k] += val; while(k > 0) { k = (k - 1) / 2; node[k] = node[2*k+1] + node[2*k+2]; } } int getsum(int a, int b, int k=0, int l=0, int r=-1) { if(r < 0) r = n; if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; int vl = getsum(a, b, 2*k+1, l, (l+r)/2); int vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } }; signed main(){ int N; cin>>N; vector<int> A(N),T(N); priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; SegmentTree s(vector<int>(N,0)); SegmentTree t(vector<int>(N,0)); for(int i=0;i<N;i++){ cin>>A[i]>>T[i]; pq.push({T[i],i}); s.add(i,A[i]); } int q; cin>>q; vector<tuple<int,int,int,int>> Q(q); vector<int> a(q); for(int i=0;i<q;i++){ int a,b,c; cin>>a>>b>>c; Q[i] = {a,b-1,c,i}; } sort(Q.begin(),Q.end()); for(int z=0;z<q;z++){ int d,l,r,i; tie(d,l,r,i) = Q[z]; while(!pq.empty() && (pq.top()).first <= d){ int x,y; tie(x,y) = pq.top(); pq.pop(); if(!t.getsum(y,y+1)){ s.add(y,T[y]-1); t.add(y,1); pq.push({A[y]+T[y],y}); } else{ s.add(y,-(A[y]+T[y]-1)); t.add(y,-1); } } a[i] = s.getsum(l,r)-t.getsum(l,r)*d; } for(int i=0;i<q;i++) cout<<a[i]<<endl; }