QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#84851 | #5657. Hungry Cow | shr_ | 0 | 2855ms | 420832kb | C++17 | 4.9kb | 2023-03-06 20:16:36 | 2023-03-06 20:16:39 |
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;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 15340kb
input:
3 4 3 1 5 1 2
output:
15 36 21
result:
wrong answer 3rd numbers differ - expected: '18', found: '21'
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 16060kb
input:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
output:
4005 4656 10731 27504 60809 1485981 1587021 1191463 4815109
result:
wrong answer 3rd numbers differ - expected: '7607', found: '10731'
Test #3:
score: 0
Wrong Answer
time: 85ms
memory: 36792kb
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:
235118030 699918971 797282574 902064730 545133458 280939836 340604482 333839266 9720010 543842184 918835528 399009519 163077436 584353639 32894659 897542719 651796867 593713660 237334343 864415848 858668186 555580288 467947892 334356890 148782995 780231816 504222094 702491808 29875558 639342623 7560...
result:
wrong answer 3rd numbers differ - expected: '430865692', found: '797282574'
Test #4:
score: 0
Memory Limit Exceeded
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
Wrong Answer
time: 2855ms
memory: 420832kb
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:
376399979 752799930 259866744 636266639 553419310 955426208 542231930 745568363 572294863 416129117 300715132 755630975 730371263 2236198 939110298 215902353 208920353 752329693 280880719 502529311 469305233 540162306 436452929 903886246 937402235 160288776 758659701 48343048 535206467 291269236 531...
result:
wrong answer 3rd numbers differ - expected: '129199846', found: '259866744'
Test #6:
score: 0
Wrong Answer
time: 2142ms
memory: 395108kb
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:
601385635 274004134 601850367 341926487 525622685 105816858 98270591 649703194 370392468 705149600 786695578 34755535 193963469 619358637 743478589 916995296 887419699 718273715 470995442 531934769 635618491 441251273 418808083 833992242 33665364 489309068 812518308 127890999 801876689 921863715 954...
result:
wrong answer 6th numbers differ - expected: '365740738', found: '105816858'
Test #7:
score: 0
Wrong Answer
time: 2127ms
memory: 384960kb
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:
805408268 531436018 27866346 628799395 526589961 842320033 947374779 840544081 578197250 176433577 251899446 704144124 43445401 416743355 194492651 393569861 450106291 695932127 282262002 71245081 657861752 753427144 472682353 431446771 898909012 760097336 22929489 305086904 745978553 402350668 8925...
result:
wrong answer 3rd numbers differ - expected: '575810846', found: '27866346'
Test #8:
score: 0
Wrong Answer
time: 2216ms
memory: 382444kb
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:
201835835 176681780 438095378 20098382 164708249 330646604 554380658 948878124 502403442 324527197 570703898 376033492 928212223 235466900 432105182 674622761 471404262 118897938 935122222 324245057 707815830 300971504 981823432 427248251 128275316 710365674 106620523 937909758 754818331 343637929 1...
result:
wrong answer 3rd numbers differ - expected: '819965610', found: '438095378'
Test #9:
score: 0
Wrong Answer
time: 2086ms
memory: 376416kb
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:
284288958 357751095 461366660 88799158 762093221 590247457 94454182 178875265 57888705 829186946 801487777 65122010 672288592 156666978 557353731 648386361 136318791 456758992 860464819 209394785 946728816 851394278 737232334 100628749 917773936 686712117 509176653 764336125 862018547 167909633 7640...
result:
wrong answer 3rd numbers differ - expected: '58956281', found: '461366660'
Test #10:
score: 0
Wrong Answer
time: 2114ms
memory: 376364kb
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:
692991104 373664255 846604839 394426111 851697704 456801584 582680219 687727357 819191446 260038216 844409456 243689313 748704439 850541794 595621419 152106562 653696590 961130674 824172930 386672291 760873389 661499404 564640640 961043408 812759050 476686347 686320784 798870136 199957839 454785766 ...
result:
wrong answer 3rd numbers differ - expected: '485258530', found: '846604839'
Test #11:
score: 0
Wrong Answer
time: 1816ms
memory: 354756kb
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:
655956691 428350171 159167788 718598219 697782676 60290222 765234432 657425973 898379955 507684503 348071114 145700257 521717103 72005509 948410215 537589376 714354605 827485360 975617113 268204252 706420543 622193221 505852834 539746758 690465404 985456282 745131482 687185541 644399345 393545009 27...
result:
wrong answer 3rd numbers differ - expected: '548564542', found: '159167788'
Test #12:
score: 0
Wrong Answer
time: 1914ms
memory: 353112kb
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:
526240962 808910950 484071840 8981473 817026076 210981320 113521579 308494502 781707132 804817601 123570495 222840685 445758439 871797808 894853599 191010567 967894416 2616394 374788440 183641375 597752620 966535525 633308293 195047663 440222754 884382615 580479201 891182096 758897401 115273049 5244...
result:
wrong answer 3rd numbers differ - expected: '692662359', found: '484071840'
Test #13:
score: 0
Wrong Answer
time: 1722ms
memory: 355008kb
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:
358833000 63285979 36439376 508625679 327759427 818027427 219457158 810202616 896331877 382564032 473921144 371494567 17613206 176627720 867222913 365948476 455768696 90616414 624354962 570993467 936745215 375188684 52989947 618496718 762528670 777116196 783453744 821321644 755151257 404879216 28560...
result:
wrong answer 3rd numbers differ - expected: '813032842', found: '36439376'
Test #14:
score: 0
Wrong Answer
time: 2160ms
memory: 214508kb
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:
700388007 142288329 334277755 410912131 137460226 411447094 72765590 279964696 222368623 890983317 250548181 402114844 415089730 858947688 522024178 316519062 847522490 40392229 942260653 18297758 528074508 595025553 517324334 218245395 762520503 900138162 528624348 779162474 27422081 1602062 752121...
result:
wrong answer 5th numbers differ - expected: '984191481', found: '137460226'
Test #15:
score: 0
Wrong Answer
time: 2362ms
memory: 370860kb
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:
656243188 689191754 943169527 417261997 171887800 942770394 487929071 540825920 189160873 266750944 983404384 360385067 283101006 109650889 640733677 287448091 620766509 782336883 375792613 606491752 337503123 827396224 298942960 229294638 564733535 633756719 762206705 377714702 706713375 885055315 ...
result:
wrong answer 3rd numbers differ - expected: '299706354', found: '943169527'
Test #16:
score: 0
Wrong Answer
time: 2232ms
memory: 223324kb
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:
123004833 323447149 549190477 181877325 102074593 684313368 487743819 426819671 65158749 306798875 973561287 33871166 212335882 447109903 319012380 889669158 963876353 496776372 363918835 241658155 462078167 859686412 929133640 369515080 711263558 149241112 172067501 56817314 411347021 205502198 677...
result:
wrong answer 5th numbers differ - expected: '350714436', found: '102074593'
Test #17:
score: 0
Wrong Answer
time: 2007ms
memory: 220428kb
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:
809311757 843230693 816940310 930310064 576914663 202937503 649004278 440287696 523152260 775851192 926032651 199093802 890061746 128914494 786259944 571978094 8544195 544032252 963947819 230934227 203630938 559839140 812622938 576473144 517822501 628817641 279065674 115218077 489559983 214009331 21...
result:
wrong answer 3rd numbers differ - expected: '330085498', found: '816940310'
Test #18:
score: 0
Wrong Answer
time: 2326ms
memory: 202128kb
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:
530050851 934114334 549124503 149653293 662653821 426576547 249451221 19812996 973822212 483604376 774679909 481877742 256424997 497248231 368156530 909359214 154282868 116727722 923056623 112502812 946532984 102752336 538391130 36466617 183517377 276794373 819039064 486866287 677649533 876378151 82...
result:
wrong answer 3rd numbers differ - expected: '139117719', found: '549124503'
Test #19:
score: 0
Wrong Answer
time: 2278ms
memory: 199408kb
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:
128224308 364130490 152929909 479550802 586285899 324788831 9199284 244116022 321041038 770371667 259990937 469741656 954528533 837855124 121709092 130114356 166490073 378283633 963080197 233134184 311265812 300703745 354988888 666412988 723713086 403206389 691696759 924763823 378102561 570462243 85...
result:
wrong answer 3rd numbers differ - expected: '758530203', found: '152929909'
Test #20:
score: 0
Wrong Answer
time: 2627ms
memory: 372516kb
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:
961356073 623334212 817690831 86852425 876836101 877388625 87058493 967071236 487128846 15353018 239000979 714101409 70166384 904225143 320506176 530484870 452070556 573710862 51539607 791278044 120476984 786764004 587762186 968746090 79533773 125391526 718492497 960896258 637952125 43647825 6565935...
result:
wrong answer 5th numbers differ - expected: '56850092', found: '876836101'
Test #21:
score: 0
Wrong Answer
time: 2131ms
memory: 197844kb
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:
92516536 444191664 406632471 93787710 625033966 763549761 999171028 521049642 40192272 530354145 529452044 887950651 520726526 627713891 581673626 525365115 241014908 546491920 511959282 892449391 23451207 719580212 115746037 558061089 901581263 963867029 428602691 855300388 705835452 143008432 7570...
result:
wrong answer 3rd numbers differ - expected: '749574507', found: '406632471'
Test #22:
score: 0
Wrong Answer
time: 2243ms
memory: 213432kb
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:
733458470 830919600 830094985 554955593 456990021 206564655 96657166 141149331 773416157 221739552 991491917 85361375 11954739 908103928 979400064 703487467 811953569 675798994 65650723 411931685 289478631 113688856 278551660 918207399 724995053 876685202 496293308 621442374 859612377 736045879 3645...
result:
wrong answer 3rd numbers differ - expected: '281776724', found: '830094985'