QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #85387 | #5657. Hungry Cow | AFewSuns | 9.090909 | 753ms | 130052kb | C++14 | 3.4kb | 2023-03-07 18:09:39 | 2023-03-07 18:09:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define ll long long
#define bl bool
ll my_pow(ll a,ll b,ll mod){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
ll qpow(ll a,ll b){
ll res=1;
if(!b) return 1;
while(b){
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
#define db double
#define pf printf
#define pc putchar
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
#define go(u) for(ll i=head[u];i;i=e[i].nxt)
#define enter pc('\n')
#define space pc(' ')
#define fir first
#define sec second
#define MP make_pair
#define il inline
#define inf 8e18
#define random(x) rand()*rand()%(x)
#define inv(a,mod) my_pow((a),(mod-2),(mod))
il ll read(){
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
sum=sum*10+(ch^48);
ch=getchar();
}
return sum*f;
}
il void write(ll x){
if(x<0){
x=-x;
pc('-');
}
if(x>9) write(x/10);
pc(x%10+'0');
}
il void writeln(ll x){
write(x);
enter;
}
il void writesp(ll x){
write(x);
space;
}
}
using namespace my_std;
#define mod 1000000007
#define LC lc[x]
#define RC rc[x]
map<ll,ll> mp;
vector<ll> vec[400040];
ll n,V=2e14,inv2=(mod+1)>>1,d[100010],b[100010],vv;
ll tree[2000020],sum[2000020],lc[2000020],rc[2000020],rt=0,tot=0,top=0;
pair<ll,pair<ll,ll> > st[2000020];
void ins(ll x,ll l,ll r,ll ql,ll qr,ll v){
if(ql<=l&&r<=qr){
vec[x].push_back(v);
return;
}
ll mid=(l+r)>>1;
if(ql<=mid) ins(x<<1,l,mid,ql,qr,v);
if(mid<qr) ins(x<<1|1,mid+1,r,ql,qr,v);
}
il ll S(ll l,ll r){
return (l+r)%mod*((r-l+1)%mod)%mod*inv2%mod;
}
il void pushup(ll x){
tree[x]=tree[LC]+tree[RC];
sum[x]=sum[LC]+sum[RC];
}
void mdf(ll &x,ll l,ll r,ll ql,ll qr){
if(!x) x=++tot;
if(tree[x]==(r-l+1)) return;
st[++top]=MP(x,MP(tree[x],sum[x]));
if(ql<=l&&r<=qr){
tree[x]=r-l+1;
sum[x]=S(l,r);
return;
}
ll mid=(l+r)>>1;
if(ql<=mid) mdf(LC,l,mid,ql,qr);
if(mid<qr) mdf(RC,mid+1,r,ql,qr);
pushup(x);
}
ll querycnt(ll x,ll l,ll r,ll ql,ll qr){
if(!x||ql>qr) return 0;
if(ql<=l&&r<=qr) return tree[x];
if(tree[x]==(r-l+1)) return min(qr,r)-max(ql,l)+1;
ll mid=(l+r)>>1,res=0;
if(ql<=mid) res+=querycnt(LC,l,mid,ql,qr);
if(mid<qr) res+=querycnt(RC,mid+1,r,ql,qr);
return res;
}
ll query(ll x,ll l,ll r,ll k){
if(l==r) return l;
ll mid=(l+r)>>1;
if((mid-l+1-tree[LC])>=k) return query(LC,l,mid,k);
else return query(RC,mid+1,r,k-(mid-l+1-tree[LC]));
}
void recycle(ll tmp){
while(top>tmp){
ll x=st[top].fir;
tree[x]=st[top].sec.fir;
sum[x]=st[top].sec.sec;
top--;
}
}
void solve(ll x,ll l,ll r){
ll tmp=top;
fr(i,0,(ll)vec[x].size()-1){
ll id=vec[x][i],cnt=d[id]-1-querycnt(rt,1,V,1,d[id]-1);
ll pos=query(rt,1,V,cnt+b[id]);
mdf(rt,1,V,d[id],pos);
}
if(l==r) writeln(sum[rt]);
else{
ll mid=(l+r)>>1;
solve(x<<1,l,mid);
solve(x<<1|1,mid+1,r);
}
recycle(tmp);
}
int main(){
n=read();
fr(i,1,n){
d[i]=read();
b[i]=read();
if(mp.count(d[i])){
ll tmp=mp[d[i]];
ins(1,1,n,tmp,i-1,tmp);
}
mp[d[i]]=i;
}
for(map<ll,ll>::iterator it=mp.begin();it!=mp.end();it++){
ll tmp=(*it).sec;
ins(1,1,n,tmp,n,tmp);
}
solve(1,1,n);
}
/*
2
1 89
30 7
ans:
4005
4656
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.54545
Accepted
time: 3ms
memory: 12792kb
input:
3 4 3 1 5 1 2
output:
15 36 18
result:
ok 3 number(s): "15 36 18"
Test #2:
score: 4.54545
Accepted
time: 1ms
memory: 12800kb
input:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
output:
4005 4656 7607 3482 3507 3753 4058 1107 24531
result:
ok 9 numbers
Test #3:
score: 0
Wrong Answer
time: 59ms
memory: 30748kb
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:
9235118093 16699919083 13430865783 22080346767 21848027473 32568710618 15340195343 24190991251 38826211930 41180951958 43569936158 49679922351 60650994368 68624850653 32428416955 32646485168 66727441089 76230674403 40429375034 41412788469 53052678941 48076241646 42668854115 45636691025 101209141239 ...
result:
wrong answer 1st numbers differ - expected: '235118030', found: '9235118093'
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:
9375000070 21250000182 39625000364 59500000581 76875000805 92750001043 108125001302 120000001561 131375001841 148250002184 162625002534 180500002933 199875003367 218750003822 229125004242 248000004746 264375005257 280250005789 296625006349 312500006930 332875007567 354750008239 376125008932 39200000...
result:
Test #5:
score: 0
Wrong Answer
time: 530ms
memory: 130052kb
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:
13376400070 34752800168 52129200210 75505600266 87882000217 109258400203 131634800168 155011200112 176387600014 196763999881 214140399699 234516799510 253893199286 267269598992 286645998712 303022398383 318398798019 337775197655 358151597270 376527996843 396904396402 417280795933 439657195450 457033...
result:
wrong answer 1st numbers differ - expected: '376399979', found: '13376400070'
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:
5601385670 19274004267 33601850598 48341926823 68525623161 77365741277 90021596975 104859481611 118580170983 135914928234 151661717192 161909777226 177068985265 191985300898 202062061390 213433239004 228022195288 228179215978 241464435392 257116142051 276069333490 277520741696 277847569597 288978626...
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:
15805408373 30531436228 41575811133 43354090254 54881282469 71197012653 89542993431 101330038414 117067691695 137366810002 148605424850 161304355142 175643656524 187699248162 200588122901 213342826955 229777770797 242872415591 255006029388 272922269154 292117630743 306092066363 318939484636 33117899...
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:
13201835926 34176682018 41819965897 53401968985 69020890959 83624222556 99244625223 113639122787 122822117702 138014404982 150994034162 164460873745 174065151504 186328332969 200840922549 211115161620 227363465238 244332156739 261785327730 274716986653 274408772036 275205349880 290098967292 30562246...
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:
15284289063 28357751291 36058956533 48911721799 61585015946 79413170308 92089222888 105932166159 123340804047 133548440840 149031416065 166677082892 180328874632 178179567077 189580253907 201559785863 218047718412 231185180446 246313962492 260337438998 271522875454 284427541007 283460972475 28425915...
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:
13692991195 24373664423 41485258817 56240812768 68150263166 78495543590 88930861594 106914610982 125046075197 138963946740 157548318106 174947598089 189579201069 199042704339 210224522220 224410017368 237535414966 250842849141 262705891481 273660699578 288310759180 301211385286 308211618354 32160802...
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:
13655956782 15428350276 11548564619 16779715331 16957292727 17681253899 18867332404 26274556440 28395033445 34333056483 37701438687 34203274108 36489695728 42706378567 16144580731 16397623838 25228896153 35520643924 34706764450 41488871851 67217476100 76415165989 66434314763 75827566527 13256029936 ...
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:
15526241067 17808911069 17692662478 18262454946 14824972025 21696977776 30511671837 30304096235 31488743132 37459596072 23852048669 23407821716 38986580607 45935810670 35447338492 41404215812 27304626730 29322322150 56109610665 62135672853 54575250886 62895904080 74120156293 80689921537 72344461690 ...
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:
15358833105 14063286077 16813032954 23736093316 16525127545 18245134126 23066495425 28919121418 10462185919 12492634598 22674820954 31065951882 33846808376 35101614570 40851611377 41714978295 36763174117 32749817314 63098970007 69753942722 65795699631 74747343691 76205026152 83285496741 76869383554 ...
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:
16700388119 29142288532 44334278063 59410912544 76984192013 96258179014 109677858058 126154120837 140441256430 154099974167 166761649346 179646693169 193083884818 208838779713 225902190369 239274896923 249996541921 264097974477 277746549988 288437181579 301944875235 319373353827 336086481181 3507457...
result:
Test #15:
score: 0
Wrong Answer
time: 753ms
memory: 125428kb
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:
11656243265 27689191943 46299706676 58773799237 73060667023 87831549715 101376708490 124384420236 137708587807 150137843009 168945050755 188282526056 205743884148 218311830215 230842913087 246958544832 258707389878 280788175219 297520783185 307118193662 320768419944 336258313150 349239966883 3651703...
result:
wrong answer 1st numbers differ - expected: '656243188', found: '11656243265'
Test #16:
score: 0
Wrong Answer
time: 695ms
memory: 125500kb
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:
10123004903 28323447345 40549190757 54181877703 65350714891 87814280511 100154145587 114531294003 126169633165 144517426310 157151044562 179211354602 193300587058 208037297443 227172489773 240594506688 256363058597 271053086947 282848436758 294973073380 310193493497 324832550346 342867274086 3611898...
result:
wrong answer 1st numbers differ - expected: '123004833', found: '10123004903'
Test #17:
score: 0
Wrong Answer
time: 727ms
memory: 125428kb
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:
16809311869 28843230889 42330085792 56443455644 70474812710 83968570030 99674644058 111484529381 124567394036 141693743621 155843925178 172034121884 188264444644 201679558839 216807568758 230593287006 244038092265 259573580427 271865486264 286067376849 299040073651 320396282000 335672782190 35043663...
result:
wrong answer 1st numbers differ - expected: '809311757', found: '16809311869'
Test #18:
score: 0
Wrong Answer
time: 742ms
memory: 125336kb
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:
21530050998 37934114593 52139118083 67739646985 85461596829 98020516254 113843391040 129256225876 140210235162 152965126335 169440165144 187147363103 200921910456 215951649990 232822558408 244173523727 264389636063 281352081036 297954190784 313647258423 330481288707 347915558467 360523390957 3756693...
result:
wrong answer 1st numbers differ - expected: '530050851', found: '21530050998'
Test #19:
score: 0
Wrong Answer
time: 734ms
memory: 125396kb
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:
15128224413 30364130700 45758530518 60303887975 72063288961 84801791984 102009196692 114270495894 131347421029 147719826754 160816622285 174790466920 186301409337 207302075535 222068533452 243076938863 259096504164 274339874986 286454714182 303072770721 319044222218 338119306129 350740303127 3646583...
result:
wrong answer 1st numbers differ - expected: '128224308', found: '15128224413'
Test #20:
score: 0
Wrong Answer
time: 703ms
memory: 125392kb
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:
10961356143 27623334401 40817691111 56086852817 73056850603 93057403267 106439227805 128440366243 146959871462 160488095732 174539037237 193014137793 209370202887 228086705052 242502986190 256003408319 269819847840 282241962892 301297676809 312744243862 327073442907 342406586522 355446452149 3728274...
result:
wrong answer 1st numbers differ - expected: '961356073', found: '10961356143'
Test #21:
score: 0
Wrong Answer
time: 726ms
memory: 125488kb
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:
18092516662 33444191895 50749574857 66436730208 84977336637 103572341931 117984215787 128916243317 144435386059 160598773462 174771547931 194406980126 206973593678 226582493461 244363678951 260678242895 271516958205 284822435308 300805169101 321893069347 335024071261 346922781011 362318946948 377630...
result:
wrong answer 1st numbers differ - expected: '92516536', found: '18092516662'
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...
output:
19733458603 32830919824 46281777046 64006637780 79090970467 95840545220 107981063181 123913346171 135545613074 150202573362 162259775974 176258392547 195911219304 205564564863 221539783506 237288652490 248397118669 264260964206 278455890172 287805327758 301682874802 315888927458 328521900107 3431615...