QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #85902 | #5657. Hungry Cow | fansizhe | 4.545455 | 247ms | 43472kb | C++23 | 2.3kb | 2023-03-08 21:01:36 | 2023-03-08 21:01:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7,inv2=5e8+4;
ll calc(ll l,ll r){return (l+r)%mod*((r-l+1)%mod)%mod*inv2%mod;}
int Q;
map<ll,pair<int,int> > mp;
vector<int*> vec;
ll siz[200005],tree[2000005];int ch[2000005][2],tot,rt;
stack<int> st;
int newnode(){
int res;
if(!st.empty())res=st.top(),st.pop();
else res=++tot;
return res;
}
void erase(int x){
tree[x]=ch[x][0]=ch[x][1]=0;
st.push(x);
}
void change(int &k,ll l,ll r,ll x,ll y){
if(!k)k=newnode();
vec.push_back(&k);
if(l>=x&&r<=y){
siz[k]=r-l+1;
tree[k]=calc(l,r);
return;
}
ll mid=l+r>>1;
if(x<=mid)change(ch[k][0],l,mid,x,y);
if(y>mid)change(ch[k][1],mid+1,r,x,y);
siz[k]=siz[ch[k][0]]+siz[ch[k][1]];
tree[k]=(tree[ch[k][0]]+tree[ch[k][1]])%mod;
}
ll query(int k,ll l,ll r,ll x){
if(!x)return 0;
if(l==r)return 1-siz[k];
if(!k)return x-l+1;
int mid=l+r>>1;
if(x<=mid)return query(ch[k][0],l,mid,x);
else return siz[ch[k][0]]+query(ch[k][1],mid+1,r,x);
}
ll find(int k,ll l,ll r,ll x){
if(l==r)return l;
if(!k)return l+x-1;
ll mid=l+r>>1,val=mid-l+1-siz[ch[k][0]];
if(x<=val)return find(ch[k][0],l,mid,x);
else return find(ch[k][1],mid+1,r,x-val);
}
void del(){
int &x=*vec.back();vec.pop_back();
siz[x]=siz[ch[x][0]]+siz[ch[x][1]];
tree[x]=(tree[ch[x][0]]+tree[ch[x][1]])%mod;
if(!siz[x])erase(x),x=0;
}
vector<pair<ll,int> >opt[400005];
void insert(int k,int l,int r,int x,int y,pair<ll,int> z){
if(l>=x&&r<=y){opt[k].push_back(z);return;}
int mid=l+r>>1;
if(x<=mid)insert(k*2,l,mid,x,y,z);
if(y>mid)insert(k*2+1,mid+1,r,x,y,z);
}
void solve(int k,int l,int r){
int now=vec.size();
for(auto p:opt[k]){
ll pos=find(rt,1,2e14,p.second+query(rt,1,2e14,p.first-1));
change(rt,1,2e14,p.first,pos);
}
if(l==r){
printf("%lld\n",tree[1]);
while(vec.size()>now)del();
return;
}
int mid=l+r>>1;
solve(k*2,l,mid);
solve(k*2+1,mid+1,r);
while(vec.size()>now)del();
}
int main(){
scanf("%d",&Q);
for(int i=1;i<=Q;i++){
ll x;int y;scanf("%lld%d",&x,&y);
if(mp.find(x)!=mp.end())insert(1,1,Q,mp[x].first,i-1,make_pair(x,mp[x].second));
mp[x]=make_pair(i,y);
}
for(auto p:mp)insert(1,1,Q,p.second.first,Q,make_pair(p.first,p.second.second));
solve(1,1,Q);
return 0;
}
詳細信息
Test #1:
score: 4.54545
Accepted
time: 6ms
memory: 13124kb
input:
3 4 3 1 5 1 2
output:
15 36 18
result:
ok 3 number(s): "15 36 18"
Test #2:
score: 0
Wrong Answer
time: 4ms
memory: 13140kb
input:
9 1 89 30 7 101 26 1 24 5 1 60 4 5 10 101 0 1 200
output:
4005 19068 19068 563886 3361172 679324894 555395214 88850629 842055867
result:
wrong answer 2nd numbers differ - expected: '4656', found: '19068'
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:
235118030 320989672 966064758 615545679 383226385 383226385 681991614 799588671 634844763 774871979 289406526 418701918 782171940 595483966 759518817 871131539 752637032 630423301 753854291 104009354 172346781 667529893 337970365 814141529 657513231 914180236 230666964 498431136 121368681 891210969 ...
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:
375000007 222353202 56709955 515808620 41515018 419442739 744285300 692370741 447066823 963087251 677662558 627989287 481204356 92152712 372367612 282907403 379051268 394097489 952234948 798949060 730853992 947844691 68602408 731908276 345231238 152613396 146986908 519248308 700759269 175268312 6723...
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:
376399979 417727312 980112158 115449069 666762861 608843427 710834544 22247970 300770298 483924829 399320377 117816697 624911486 623709785 166673293 896700551 911521915 108515255 572489843 339309412 151988928 933464060 436059404 127707167 280522757 302929815 69547401 412515370 980684529 180774204 93...
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:
601385635 918401605 210076892 486488683 27189710 814263250 775430730 314313480 113792173 953459969 365633230 566141154 216840174 397977326 272912311 809894531 95273188 95273188 393499265 351319179 686880559 686880559 686880559 80617149 927744992 629777458 629777458 765047656 695178334 216120529 5869...
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:
805408268 665914370 74709017 399537624 355765202 539710396 958471597 544712027 346671186 287338771 8768415 892213902 238411724 775127063 857814089 744026860 5955606 705395490 472328223 985349384 903613148 455358430 86530498 149991042 707400190 289343378 455220043 225513440 196276385 196276385 990565...
result:
Test #8:
score: 0
Wrong Answer
time: 233ms
memory: 39036kb
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 833279558 833279558 15215072 124902267 809830444 966590616 956222851 238024150 406014680 684156137 977610684 554638402 301404403 396222698 201319088 418483163 52358470 489684639 764799616 764799616 764799616 764799616 832380050 832380050 583485247 182263282 267699687 773153421 583460765 12...
result:
wrong answer 2nd numbers differ - expected: '176681780', found: '833279558'
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:
284288958 404892669 202857188 409265855 510053278 270933430 45066486 968534694 18657576 347566916 491041751 835644776 825813193 489526028 761912555 195988423 390368233 455799234 896627827 905926638 883943953 987379661 996678472 996678472 350047786 265792942 826612727 501188660 799536695 16253852 437...
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:
692991104 549190661 337329284 454013638 454881026 778753139 743181664 319304772 555746919 728692059 800294607 18529380 57515417 81724914 90756550 977747957 616158387 758036803 26804729 845475059 940260581 476284048 681393023 735996119 621509325 213653385 590795856 54596795 636469601 301948958 763704...
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:
655956691 519112513 689449413 373887765 67592584 584724746 745292200 724100867 234902791 207977609 50955622 519953553 445083902 15608562 15608562 824208804 15608562 89983602 89983602 15608562 15608562 705390621 15608562 634367893 634367893 15608562 15608562 635677204 15608562 766080214 766080214 156...
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:
526240962 81861050 878089956 772427666 463372930 349295495 213152510 442894187 809840365 455226231 762562336 561526575 93533262 299264535 299264535 915528508 299264535 334035720 334035720 299264535 299264535 969841177 299264535 578804990 578804990 299264535 299264535 293150697 299264535 532850044 53...
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:
358833000 366845731 538538189 471878722 963103385 671427310 81932107 301885757 25677041 408378409 822963220 284020755 279306556 226049310 758714579 147505273 378290406 147275639 147275639 378290406 378290406 442010989 378290406 500590958 500590958 378290406 378290406 721699464 378290406 804319088 80...
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:
700388007 481923600 375888299 596991361 934304806 58262556 888278638 661224352 920866137 767032607 998552847 579525407 294473691 590786938 423357172 269081874 672326700 704686466 571159243 637242251 509009700 293515998 293515998 943966108 597349752 601148171 884044040 344786843 992115025 735340461 2...
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:
656243188 369773520 268420162 4078868 960363891 984022366 770093836 73821401 119479243 400469687 704599507 165754362 542308791 285115115 742011779 934927695 696842208 80351715 80351715 126590793 646422389 834766391 650770337 935211489 286539923 581190818 237776282 727426771 535389584 302019356 30201...
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:
123004833 627192508 353831554 982381928 328614583 831441185 187448682 482756510 303492670 433024989 155354712 680132505 676420937 559782132 566081216 260002969 588208769 242203785 826127957 242203785 402434630 975618319 916341141 157411932 473251737 944484927 658803569 845413391 671398388 320944262 ...
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:
809311757 222209335 518984504 695251876 539099547 938173270 772907014 17822038 633507336 602898988 337346330 74773995 982281662 297543694 208079888 7713122 556203862 383808303 871543207 43938759 223164379 670551904 45841863 666178915 330770059 429166328 466174254 466174254 988896409 644829618 298449...
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:
530050851 445062903 808427670 516504219 540005970 865852149 583028962 258966782 183433926 514341012 946528953 199375636 49589844 963600287 83407809 367147251 153009350 233803383 163536493 167120193 651772422 104363924 805630267 193225200 413777257 460945563 386191846 201479706 144139418 475308293 47...
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:
128224308 956388111 46377725 764639764 133709944 606265598 297505680 689942673 277376701 119486407 240942028 523659281 562376092 490373218 83099303 384179696 95849078 186753330 252578128 189089932 750263455 245245836 372650689 374822297 299438554 276288738 919636380 632885173 888707931 315511766 486...
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:
961356073 221498148 400897902 433523046 113604601 782485256 714148123 854050829 327427456 615181771 197041658 785958639 151299634 148596312 989116304 617432354 617432354 616377124 922852532 371589363 361302383 763416953 752456679 458246574 577545340 834488955 265672761 537038608 537038608 626430469 ...
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:
92516536 902499832 960559231 161938082 405626841 298355816 418883250 190634908 302744915 636010949 475468181 870362062 239127293 98681274 699945679 215235058 641795385 645519981 645519981 159939741 335286356 656296148 943723087 708291428 822700498 265736757 383234364 271944202 386835802 827147665 75...
result:
Test #22:
score: 0
Wrong Answer
time: 247ms
memory: 43472kb
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 379182873 822995803 644338276 812130821 446251600 34555670 597592508 524145680 474868957 312683966 993245538 933533325 799581578 639981166 351544487 979760888 840455252 892280124 128433094 975972941 137790954 917617792 369643320 36583697 544742231 726539408 209967911 209967911 251397862 25...
result:
wrong answer 2nd numbers differ - expected: '830919600', found: '379182873'