QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85387#5657. Hungry CowAFewSuns9.090909 753ms130052kbC++143.4kb2023-03-07 18:09:392023-03-07 18:09:43

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-07 18:09:43]
  • 评测
  • 测评结果:9.090909
  • 用时:753ms
  • 内存:130052kb
  • [2023-03-07 18:09:39]
  • 提交

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
*/

详细

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...

result: