QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#84930#5657. Hungry CowAl_fly9.090909 2311ms440688kbC++142.1kb2023-03-06 21:05:062023-03-06 21:05:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 21:05:15]
  • 评测
  • 测评结果:9.090909
  • 用时:2311ms
  • 内存:440688kb
  • [2023-03-06 21:05:06]
  • 提交

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'