QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#84930 | #5657. Hungry Cow | Al_fly | 9.090909 | 2311ms | 440688kb | C++14 | 2.1kb | 2023-03-06 21:05:06 | 2023-03-06 21:05:15 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,mod=1e9+7,inv2=5e8+4;
int n,m,cnt,tg[N*150],rt,ls[N*150],rs[N*150],sz[N*150],sum[N*150],lim=1e14;
vector<pair<int,int>>t[N<<2];
inline int s(int l,int r){
return (l+r)*(r-l+1)%mod*inv2%mod;
}
inline void pushup(int x){
sz[x]=sz[ls[x]]+sz[rs[x]],sum[x]=(sum[ls[x]]+sum[rs[x]])%mod;
}
inline int update(int y,int l,int r,int ql,int qr){
int x=++cnt;
ls[x]=ls[y],rs[x]=rs[y],sz[x]=sz[y],sum[x]=sum[y],tg[x]=tg[y];
if(ql>qr||tg[x])return x;
if(l>=ql&&r<=qr){
tg[x]=1,sum[x]=s(l,r),sz[x]=r-l+1;return x;
}
int mid=(l+r)>>1;
if(ql<=mid)ls[x]=update(ls[y],l,mid,ql,qr);
if(qr>mid)rs[x]=update(rs[y],mid+1,r,ql,qr);
pushup(x);
return x;
}
inline int ask(int x,int l,int r,int ql,int qr){
if(ql>qr||l>qr||r<ql||tg[x])return 0;
if(!x)return min(qr,r)-max(l,ql)+1;
if(l>=ql&&r<=qr)return r-l+1-sz[x];
int mid=(l+r)>>1;
return ask(ls[x],l,mid,ql,qr)+ask(rs[x],mid+1,r,ql,qr);
}
inline int find(int x,int l,int r,int k){
if(!x)return l+k-1;
int mid=(l+r)>>1;
int c=mid-l+1-sz[ls[x]];
if(c>=k)return find(ls[x],l,mid,k);
else return find(rs[x],mid+1,r,k-c);
}
inline void add(int x,int l,int r,int ql,int qr,pair<int,int> k){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){
t[x].push_back(k);return;
}
int mid=(l+r)>>1;
add(x<<1,l,mid,ql,qr,k),add(x<<1|1,mid+1,r,ql,qr,k);
}
inline void sol(int x,int l,int r){
int now=cnt,np=rt;
for(auto v:t[x]){
rt=update(rt,1,lim,v.first,find(rt,1,lim,ask(rt,1,lim,1,v.first-1)+v.second));
}
int mid=(l+r)>>1;
if(l==r)cout<<sum[rt]<<'\n';
else sol(x<<1,l,mid),sol(x<<1|1,mid+1,r);
for(int i=now+1;i<=cnt;i++)ls[i]=rs[i]=tg[i]=sum[i]=sz[i]=0;
rt=np,cnt=now;
}
map<int,pair<int,int>>mp;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int a,b;
cin>>a>>b;
if(mp.count(a))add(1,1,n,mp[a].first,i-1,{a,mp[a].second});
mp[a]={i,b};
}
for(auto v:mp){
add(1,1,n,v.second.first,n,{v.first,v.second.second});
}
sol(1,1,n);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 4.54545
Accepted
time: 1ms
memory: 13084kb
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: 13408kb
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: 33ms
memory: 29832kb
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 430865692 80346613 848027326 568710394 340195238 190991083 826211664 180951671 569935857 679922008 650993948 624850177 428416731 646484944 727440627 230673871 429374754 412788182 52678570 76241310 668853821 636690710 209140532 869111458 915919167 837020724 313374684 328391122 903...
result:
wrong answer 2501st numbers differ - expected: '948499983', found: '53943131'
Test #4:
score: 0
Wrong Answer
time: 1448ms
memory: 440688kb
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 250000035 625000091 500000168 875000273 750000399 125000546 721 375000924 250001148 625001400 500001673 875001974 750002296 833830642 708831013 792659408 667659828 42660269 626488741 1489231 876489756 251490295 126490862 210319453 794148072 877976712 461805373 254462058 838290775 922119513...
result:
wrong answer 15th numbers differ - expected: '125002639', found: '833830642'
Test #5:
score: 0
Wrong Answer
time: 1884ms
memory: 242068kb
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:
-408553341 -108278707 483167903 74614478 374889028 675163550 266610041 -141943496 449502946 40949353 632395739 932670093 815288420 406734715 998180989 298455224 889901442 772519629 781621783 373067910 964514016 555960087 856234133 738852152 621470143 212916102 95534037 978151951 278425822 161043673 ...
result:
wrong answer 1st numbers differ - expected: '376399979', found: '-408553341'
Test #6:
score: 0
Wrong Answer
time: 638ms
memory: 117576kb
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 323859412 59406639 419642292 -359861925 -519743872 -464852751 -782257520 -638621026 -490043254 43898578 208236560 95237708 376660024 589188239 71603545 122894691 988743384 698146542 817585055 845329456 296737648 458877540 725702527 739705208 132747396 608642451 763256475 326069548 -6222044...
result:
wrong answer 2nd numbers differ - expected: '274004134', found: '323859412'
Test #7:
score: 0
Wrong Answer
time: 589ms
memory: 108932kb
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:
594698891 837580663 881955491 369062594 735904033 893421050 584536465 410465711 63160276 -314360856 440825226 -243406424 138771784 232682263 340878886 66327033 108657314 523509148 267715878 437321130 57316932 47846806 773789510 749978109 825962453 327328887 -302258161 9949212 -264514767 391857355 67...
result:
wrong answer 1st numbers differ - expected: '805408268', found: '594698891'
Test #8:
score: 0
Wrong Answer
time: 544ms
memory: 102024kb
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:
869703869 224231614 -173276732 -221494030 -501687012 -352245682 -201597819 -592504184 -283025337 300365087 -567525375 -320846858 -714316614 -799246647 -972527373 -997843152 -863921866 -371565908 -545408879 -421996755 -21383369 -515977536 -831099762 -118152108 -321695728 -95441926 -126133753 -2470414...
result:
wrong answer 1st numbers differ - expected: '201835835', found: '869703869'
Test #9:
score: 0
Wrong Answer
time: 486ms
memory: 91664kb
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:
-155644503 -54048261 -352843075 61393068 -404172224 -594187962 196759287 588400453 344646229 121067867 -110182015 52789219 -351289727 208230735 680149206 -170171899 -332546700 -133136837 727095302 973047262 196466959 85886202 -463026331 335158218 -564960270 -834434662 -52762288 -407460693 -316359003...
result:
wrong answer 1st numbers differ - expected: '284288958', found: '-155644503'
Test #10:
score: 0
Wrong Answer
time: 456ms
memory: 85804kb
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:
51119531 -255151632 -15889629 250273107 627119787 390056133 40138036 373800756 279927560 724837847 829101768 275030437 93378094 683365296 218983350 941304440 222221062 347132763 -14040555 791219904 654356244 402563825 715124599 747887023 689163859 154856180 984051455 755747712 335762843 24456025 332...
result:
wrong answer 1st numbers differ - expected: '692991104', found: '51119531'
Test #11:
score: 0
Wrong Answer
time: 498ms
memory: 101508kb
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:
98990833 -128615687 -550403666 -319252989 273109540 -2929295 -371679011 35544976 -11819619 -73796623 -671936232 -461272787 -239387256 -22704459 -30680699 222362408 -333246190 -41498489 -385676153 -603568801 -336566472 -138876646 -617616606 -224364905 -101586056 -520489407 -137984315 -675093387 11426...
result:
wrong answer 1st numbers differ - expected: '655956691', found: '98990833'
Test #12:
score: 0
Wrong Answer
time: 577ms
memory: 95408kb
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:
-623306613 -631808629 -402533961 -832741500 -594424101 -722418399 639171555 431595953 202128910 172981808 162468434 -281758519 811990223 761220237 77117171 33994449 172127236 189822642 339399779 365461925 798176571 118829702 88029093 657794295 79568354 63226927 -47649900 -413366306 -251520755 -20971...
result:
wrong answer 1st numbers differ - expected: '526240962', found: '-623306613'
Test #13:
score: 0
Wrong Answer
time: 496ms
memory: 97808kb
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:
389219660 93672639 984416494 907476807 250783003 970789577 927803723 780429674 776713270 807161935 830339922 221470787 21816 254828003 460852581 324219492 967982843 954626068 369886841 24859507 353062649 304706646 738194683 818665223 417913208 175882412 812990494 871753454 980062863 8584703 16970907...
result:
wrong answer 1st numbers differ - expected: '358833000', found: '389219660'
Test #14:
score: 0
Wrong Answer
time: 2271ms
memory: 176360kb
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:
928993780 233439176 -187240044 317067351 -174975492 -303901804 -334623843 183614726 736491186 392285070 79673908 272602307 -21594311 -25939091 249929978 623537463 -261523841 -377160803 -154624158 -149412334 -77659653 -824840127 -512488421 -564980985 -576051253 -356936332 -593017953 -649516361 941118...
result:
wrong answer 1st numbers differ - expected: '700388007', found: '928993780'
Test #15:
score: 0
Wrong Answer
time: 2023ms
memory: 176580kb
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:
791958092 71126109 -70452700 -126711309 800906241 748295901 664638698 968645708 317573020 822564966 390310786 900803850 948560423 435036972 867884781 251792638 427975019 654827730 119954590 167995811 206904889 534026936 513940556 428092104 52118547 57744428 873559365 250071834 618421127 18347623 629...
result:
wrong answer 1st numbers differ - expected: '656243188', found: '791958092'
Test #16:
score: 0
Wrong Answer
time: 2311ms
memory: 176356kb
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:
-154943685 -522270358 -213140648 469003863 388362161 858455470 575917507 -39337517 172344482 347517227 523588249 -11554448 106262526 104438483 -126597819 -818459822 -473976949 -83220766 -508146925 380234293 264414844 -663228579 -942519853 -609920351 61263235 609480116 937603017 633679132 473907183 7...
result:
wrong answer 1st numbers differ - expected: '123004833', found: '-154943685'
Test #17:
score: 0
Wrong Answer
time: 2193ms
memory: 176364kb
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:
378997694 -183154264 313267057 -75527281 -35389915 472942333 -392241917 -721498737 -780081676 -137160899 372500527 -177524342 489304612 723247866 269646894 418952499 214572140 471325568 223764237 267326758 203003188 -290445805 551014425 602044058 223941640 187114592 360011268 -122096200 481255410 -1...
result:
wrong answer 1st numbers differ - expected: '809311757', found: '378997694'
Test #18:
score: 0
Wrong Answer
time: 2097ms
memory: 178072kb
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:
-369965022 -731386241 -254114041 -906721041 -214928154 -314928649 -607452128 -603157398 -65002137 -143002691 -779705177 -558073677 -128148652 -84284715 -701363111 -256826667 -147897648 -210433322 -87026583 -137219178 369404820 471542488 553016385 832451344 569159740 882501647 718168321 857343259 529...
result:
wrong answer 1st numbers differ - expected: '530050851', found: '-369965022'
Test #19:
score: 0
Wrong Answer
time: 2076ms
memory: 176420kb
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:
67177410 -422960474 -560996602 -392670873 171434678 -225096961 545297929 119375306 109822385 272304732 232546268 192831719 928555055 121592702 439787173 435534373 645333521 753837467 90586702 719896771 404734151 -189004016 103350102 330112232 564010940 301433163 117297968 743800721 453796629 4975431...
result:
wrong answer 1st numbers differ - expected: '128224308', found: '67177410'
Test #20:
score: 0
Wrong Answer
time: 2005ms
memory: 176636kb
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:
-101263054 410602102 719067363 205077688 13540923 307182406 295209671 -410563093 39795037 -20622813 358290190 103804488 536675120 -251742895 2835913 -205455141 243969679 544273562 907536413 182216330 435404871 313085990 271482099 717399700 2600194 585762964 468463710 64612923 567688121 178537645 107...
result:
wrong answer 1st numbers differ - expected: '961356073', found: '-101263054'
Test #21:
score: 0
Wrong Answer
time: 1956ms
memory: 176512kb
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:
-506760824 -455426587 -979896721 -406620295 -242312400 -299080914 -112041041 -641385511 -613153324 -192858355 -72633195 12528652 171503141 166833123 216179807 544417636 611403042 642420713 -91323163 523783578 -92582216 368048929 41492072 105296332 -115127706 604206380 -18772517 420362555 288771142 -...
result:
wrong answer 1st numbers differ - expected: '92516536', found: '-506760824'
Test #22:
score: 0
Wrong Answer
time: 2074ms
memory: 176360kb
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:
154435839 150958924 -465025471 -357391501 -300627602 -927634087 -104955868 -763117063 -452346879 49041300 -580076891 -267330617 -239044592 -55118195 172450015 -290123712 -234657332 -431576094 -208516121 319451208 558615765 701483781 286350216 -66114676 13220802 440877689 916785744 603397469 49053077...
result:
wrong answer 1st numbers differ - expected: '733458470', found: '154435839'