QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#84849 | #5657. Hungry Cow | shr_ | 0 | 0ms | 0kb | C++17 | 4.9kb | 2023-03-06 20:15:48 | 2023-03-06 20:15:50 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7,inv=5e8+4;
const long long inf=2e14;
int n,ans[100010],ro;
pair<long long,int> op[100010];
map<long long,pair<int,int> > mp;
struct Second_Segment_Tree {
int cnt=0;
vector<int> bin;
struct node {
int son[2],sum;
long long cnt;
} f[10000010];
struct operation {
int x,opt;
long long vl;
operation() {}
operation(int _x,int _opt,long long _vl) { x=_x, opt=_opt, vl=_vl;}
};
vector<operation> op;
int new_() {
if (!bin.empty()) return ++cnt;
int x=bin.back(); bin.pop_back();
return x;
}
void erase_(int x) {
f[x].son[0]=f[x].son[1]=f[x].sum=f[x].cnt=0;
bin.push_back(x);
}
void pushup_(int x) {
op.push_back(operation(x,1,f[x].sum)), f[x].sum=(f[f[x].son[0]].sum+f[f[x].son[1]].sum)%mod;
op.push_back(operation(x,2,f[x].cnt)), f[x].cnt=f[f[x].son[0]].cnt+f[f[x].son[1]].cnt;
}
int cover_(int x,long long l,long long r,long long lpos,long long rpos) {
if (!x) x=new_(), op.push_back(operation(x,3,0));
if (f[x].cnt==r-l+1) return x;
if (lpos<=l&&r<=rpos) {
op.push_back(operation(x,1,f[x].sum)), f[x].sum=(l+r)%mod*((r-l+1)%mod)%mod*inv%mod;
op.push_back(operation(x,2,f[x].cnt)), f[x].cnt=r-l+1;
return x;
}
long long mid=(l+r)>>1;
if (lpos<=mid) f[x].son[0]=cover_(f[x].son[0],l,mid,lpos,rpos);
if (mid<rpos) f[x].son[1]=cover_(f[x].son[1],mid+1,r,lpos,rpos);
pushup_(x);
return x;
}
pair<long long,long long> check_prefix_(int x,long long l,long long r,long long lpos,int kl) {
if (!x&&r-max(lpos,l)+1<kl) return make_pair(1e18+7,r-max(lpos,l)+1);
if (!x) return make_pair(max(lpos,l)+kl-1,0);
if (f[x].cnt==r-l+1) return make_pair(1e18+7,0);
if (lpos<=l&&r-l+1-f[x].cnt<kl) return make_pair(1e18+7,r-l+1-f[x].cnt);
if (l==r) return make_pair(l,0);
long long mid=(l+r)>>1;
if (lpos>mid) return check_prefix_(f[x].son[1],mid+1,r,lpos,kl);
auto e=check_prefix_(f[x].son[0],l,mid,lpos,kl);
if (e.first==1e18+7) {
auto o=check_prefix_(f[x].son[1],mid+1,r,lpos,kl-e.second);
if (o.first==1e18+7) return make_pair(1e18+7,e.second+o.second);
return o;
}
return e;
}
int check_sum_(int x,long long l,long long r,long long lpos,long long rpos) {
if (!x) return 0;
if (f[x].cnt==r-l+1) {
lpos=max(lpos,l), rpos=min(rpos,r);
return (lpos+rpos)%mod*((rpos-lpos+1)%mod)%mod*inv%mod;
}
if (lpos<=l&&r<=rpos) return f[x].sum;
int ans=0;
long long mid=(l+r)>>1;
if (lpos<=mid) ans=(ans+check_sum_(f[x].son[0],l,mid,lpos,rpos))%mod;
if (mid<rpos) ans=(ans+check_sum_(f[x].son[1],mid+1,r,lpos,rpos))%mod;
return ans;
}
int check_ver_() { return op.size();}
void rollback_(int ver) {
while ((int)op.size()>ver) {
operation e=op[(int)op.size()-1]; op.pop_back();
if (e.opt==1) f[e.x].sum=e.vl;
if (e.opt==2) f[e.x].cnt=e.vl;
if (e.opt==3) erase_(e.x);
}
}
} sst;
struct First_Segment_Tree {
struct node { vector<pair<long long,int> > op;} f[400010];
void insert_(int k,int l,int r,int lpos,int rpos,pair<long long,int> key) {
if (key.second==0) return;
if (lpos<=l&&r<=rpos) { f[k].op.push_back(key); return;}
int mid=(l+r)>>1;
if (lpos<=mid) insert_(k<<1,l,mid,lpos,rpos,key);
if (mid<rpos) insert_(k<<1|1,mid+1,r,lpos,rpos,key);
}
void solve_(int k,int l,int r) {
int ver=sst.check_ver_();
for (auto o : f[k].op) {
long long lr=sst.check_prefix_(ro,1,inf,o.first,o.second).first;
ro=sst.cover_(ro,1,inf,o.first,lr);
}
if (l==r) { ans[l]=sst.check_sum_(ro,1,inf,1,inf), sst.rollback_(ver); return;}
int mid=(l+r)>>1;
solve_(k<<1,l,mid), solve_(k<<1|1,mid+1,r);
sst.rollback_(ver);
}
} fst;
int main() {
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld %d\n",&op[i].first,&op[i].second);
for (int i=1;i<=n;i++) {
if (mp.count(op[i].first)) fst.insert_(1,1,n,mp[op[i].first].first,i-1,pair<long long,int> (op[i].first,mp[op[i].first].second));
mp[op[i].first]=pair<int,int> (i,op[i].second);
}
for (int i=1;i<=n;i++) if (mp.count(op[i].first)) fst.insert_(1,1,n,mp[op[i].first].first,n,pair<long long,int> (op[i].first,mp[op[i].first].second)), mp.erase(op[i].first);
fst.solve_(1,1,n);
for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 4 3 1 5 1 2
output:
result:
Test #2:
score: 0
Runtime Error
input:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
output:
result:
Test #3:
score: 0
Runtime Error
input:
5000 1 255364995 414918035 212844 1 112266691 321122438 191414 1 277615842 848755093 61676 1 432591689 892259443 53755 1 263753018 173404455 173565 1 178341924 878941367 221276 1 65332960 439468128 240741 1 812238377 191076090 108732 1 180383041 927440330 112995 1 595696140 579818784 85614 1 5057816...
output:
result:
Test #4:
score: 0
Runtime Error
input:
100000 1 500000000 1000000001 500000000 2000000001 500000000 3000000001 500000000 4000000001 500000000 5000000001 500000000 6000000001 500000000 7000000001 500000000 8000000001 500000000 9000000001 500000000 10000000001 500000000 11000000001 500000000 12000000001 500000000 13000000001 500000000 1400...
output:
result:
Test #5:
score: 0
Runtime Error
input:
100000 49998999950002 500000000 49997999950003 500000000 49996999950004 500000000 49995999950005 500000000 49994999950006 500000000 49993999950007 500000000 49992999950008 500000000 49991999950009 500000000 49990999950010 500000000 49989999950011 500000000 49988999950012 500000000 49987999950013 500...
output:
result:
Test #6:
score: 0
Runtime Error
input:
100000 92303348842417 121458 92270522994821 852054850 93765096269940 752161890 97779083359973 984327853 90030769679569 439157849 99462493683485 45660 95578441605501 614317411 92236129196525 474149928 96065411631989 429943696 90394247621798 382840249 89263934750729 791122796 93577089467158 99679481 9...
output:
result:
Test #7:
score: 0
Runtime Error
input:
100000 98001410246890 641673458 94816407430628 495030536 95979591652947 43208 95979591652947 183686 97163521776290 904784415 91640049592559 875129980 95914835187460 844802426 94846379383324 974270031 99639652388956 311664277 99298294827771 913614463 99476866913169 221766107 97248342663994 669489020 ...
output:
result:
Test #8:
score: 0
Runtime Error
input:
100000 97338601145206 191999210 97657969728741 875988993 92559675348135 8552565 99354409480201 960853995 93648768326445 343671323 97400841247229 104463842 98844341051398 508718383 96144328794112 187050711 98030257583732 365513 92378049740181 852725611 98301676983212 360931360 99458914124366 80234576...
output:
result:
Test #9:
score: 0
Runtime Error
input:
100000 96119987448606 658315028 98644701118435 280992389 98180676447908 56168 99822794299596 237183170 94655838918825 563695131 95744558879343 686204820 93739311062176 263266841 97630990881452 96901680 98683433984282 380708175 98141920320037 147598812 98095513966598 814629225 97882900659205 55097258...
output:
result:
Test #10:
score: 0
Runtime Error
input:
100000 98169641631056 170946511 99452522210742 393032132 98797460964704 393706377 98747209012224 529219651 99152468691953 362194103 99410753036475 215295 97096873124809 1315725 96106202009957 124516158 95176405230280 853965254 99359463136784 622839995 96635771520630 550456203 96368792029394 93630831...
output:
result:
Test #11:
score: 0
Runtime Error
input:
100000 97499080763005 475255826 97499083333242 9347 97499080763005 395470349 97499924236501 4654 97499080763005 148122052 97499213182916 2365 97499080763005 544025506 97499777050346 9912 97499080763005 41736833 97499401163067 12607 97499080763005 127843558 97499125181305 7144 97499080763005 13152858...
output:
result:
Test #12:
score: 0
Runtime Error
input:
100000 98999026537234 929244389 98999182418499 5182 98999026537234 774643967 98999646433835 17857 98999026537234 760743518 98999980664456 7597 98999026537234 573421161 98999090975969 6621 98999026537234 95191521 98999947586610 17798 98999026537234 953104244 98999116462517 15643 98999026537234 100617...
output:
result:
Test #13:
score: 0
Runtime Error
input:
100000 99499024212061 630391525 99499061152079 3864 99499024212061 16505706 99499878275777 4812 99499024212061 776185964 99499757280269 12059 99499024212061 356565635 99499399237611 8902 99499024212061 972528120 99499256994518 9171 99499024212061 419476867 99499909552451 17146 99499024212061 6767939...
output:
result:
Test #14:
score: 0
Runtime Error
input:
99999 10490328589436 1000000000 13762508396295 1000000000 40632115714511 1000000000 32834989282081 1000000000 29091918306598 1000000000 24352818172350 1000000000 23447797352860 1000000000 38073075086135 1000000000 14288530509239 1000000000 36463049009868 1000000000 10562334120356 1000000000 34490016...
output:
result:
Test #15:
score: 0
Runtime Error
input:
99999 61585049539216 1000000000 58981995705940 1000000000 44247484521936 1000000000 70916218483207 1000000000 47696673638497 1000000000 60781033156530 1000000000 55859922511212 1000000000 59143999312357 1000000000 57175954090596 1000000000 71328224891428 1000000000 46047599292678 1000000000 47510666...
output:
result:
Test #16:
score: 0
Runtime Error
input:
99999 21219982576425 1000000000 42260400232639 1000000000 26412110792985 1000000000 11035481121988 1000000000 13219690258669 1000000000 19550933913223 1000000000 32679237390903 1000000000 15679803374289 1000000000 23896051833122 1000000000 20099950455987 1000000000 14778766729432 1000000000 21547991...
output:
result:
Test #17:
score: 0
Runtime Error
input:
99999 28503598869279 1000000000 32397709666940 1000000000 25833502058723 1000000000 38020841213328 1000000000 54560138759501 1000000000 42230929758874 1000000000 28972613620824 1000000000 28498598787317 1000000000 54070131397843 1000000000 22084267818956 1000000000 37776835952805 1000000000 44465973...
output:
result:
Test #18:
score: 0
Runtime Error
input:
99999 18175781548542 1000000000 40883228277118 1000000000 33828113807745 1000000000 17817771477758 1000000000 22749897023579 1000000000 18015777423352 1000000000 28920025506062 1000000000 18799798298070 1000000000 27979006765970 1000000000 17103749421004 1000000000 24329932307643 1000000000 29798042...
output:
result:
Test #19:
score: 0
Runtime Error
input:
99999 13631696063382 1000000000 19095823575649 1000000000 18048800926387 1000000000 17060779354093 1000000000 15768748767399 1000000000 30886037572930 1000000000 26814970558482 1000000000 8165534157289 1000000000 27914989206121 1000000000 34170089895536 1000000000 27764986366439 1000000000 145187181...
output:
result:
Test #20:
score: 0
Runtime Error
input:
99999 71091006018203 1000000000 42267334298998 1000000000 53421686894439 1000000000 52992676205010 1000000000 49055576058012 1000000000 70721000416119 1000000000 43151374327143 1000000000 70716000332404 1000000000 51528640431406 1000000000 65945925001029 1000000000 39524135856472 1000000000 66414932...
output:
result:
Test #21:
score: 0
Runtime Error
input:
99999 43981987091230 1000000000 41793950053258 1000000000 23385527966154 1000000000 32049759202175 1000000000 48927065970165 1000000000 26694629471843 1000000000 27661655640242 1000000000 37241867113918 1000000000 49110069037684 1000000000 20323405372655 1000000000 43304975621086 1000000000 48021052...
output:
result:
Test #22:
score: 0
Runtime Error
input:
99999 31159466866911 1000000000 28413414847308 1000000000 25948364344910 1000000000 31236468095715 1000000000 22036273821032 1000000000 24056321657736 1000000000 36031551606814 1000000000 37935581367999 1000000000 40624624246259 1000000000 18857191994835 1000000000 22179277697755 1000000000 29154428...