QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#85553#5657. Hungry CowBird9.090909 3726ms177076kbC++142.6kb2023-03-07 21:00:012023-03-07 21:00:09

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 21:00:09]
  • 评测
  • 测评结果:9.090909
  • 用时:3726ms
  • 内存:177076kb
  • [2023-03-07 21:00:01]
  • 提交

answer

#include<bits/stdc++.h>
#define N 100000
using namespace std;
const int mod=1e9+7;
const long long lim=2e14;
int n,b;long long d;
inline int fmod(int x) {return x>=mod?x-mod:x;}
inline int sum(long long l,long long r) {return ((__int128)(l+r)*(r-l+1)>>1)%mod;}
#define mid ((l+r)>>1)
namespace segment_tree2
{
	int tot=0,root;
	struct node
	{
		int lson,rson,val,sum;
		long long siz;
	}t[N<<8];
	inline void push_up(int x,long long l,long long r)
	{
		if(t[x].val) return t[x].siz=r-l+1,t[x].sum=sum(l,r),void();
		if(l==r) return t[x].siz=0,t[x].sum=0,void();
		t[x].siz=t[t[x].lson].siz+t[t[x].rson].siz;
		t[x].sum=fmod(t[t[x].lson].sum+t[t[x].rson].sum);
	}
	inline void modify(int &x,long long l,long long r,long long le,long long ri,int v)
	{
		if(l>ri || r<le || le>ri) return;if(!x) x=++tot;
		if(le<=l && r<=ri) return t[x].val+=v,push_up(x,l,r);
		modify(t[x].lson,l,mid,le,ri,v),modify(t[x].rson,mid+1,r,le,ri,v),push_up(x,l,r);
	}
	inline long long query(long long x,long long l,long long r,long le,long long ri)
	{
		if(l>ri || r<le || le>ri || t[x].val) return 0;
		if(le<=l && r<=ri) return r-l+1-t[x].siz;
		return query(t[x].lson,l,mid,le,ri)+query(t[x].rson,mid+1,r,le,ri);
	}
	inline long long find(int x,long long l,long long r,long long k)
	{
		if(l==r) return l;
		long long lval=mid-l+1-t[t[x].lson].siz;
		if(k<=lval) return find(t[x].lson,l,mid,k);
		return find(t[x].rson,mid+1,r,k-lval);
	}
}
using namespace segment_tree2;
namespace segment_tree1
{
	#define lson x<<1
	#define rson x<<1|1
	vector<pair<long long,int>> que[N*4];
	inline void insert(int x,int l,int r,int le,int ri,int b)
	{
		if(l>ri || r<le) return;
		if(le<=l && r<=ri) return que[x].push_back({d,b});
		insert(lson,l,mid,le,ri,b),insert(rson,mid+1,r,le,ri,b);
	}
	inline void solve(int x,int l,int r)
	{
		vector<pair<long long,long long>> modi;
		for(pair<int,long long> p:que[x])
		{
			long long num=query(root,1,lim,1,p.first-1);
			long long le=find(root,1,lim,num+1),ri=find(root,1,lim,num+p.second);
			modify(root,1,lim,le,ri,1),modi.push_back({le,ri});
		}
		if(l==r) printf("%d\n",t[root].sum);
		else solve(lson,l,mid),solve(rson,mid+1,r);
		for(pair<long long,long long> p:modi)
			modify(root,1,lim,p.first,p.second,-1);
	}
	#undef lson
	#undef rson
}
using namespace segment_tree1;
int main()
{
	scanf("%d",&n);
	map<long long,pair<int,int>> last;
	for(int i=1;i<=n;last[d]={i++,b})
	{
		scanf("%lld %d",&d,&b);
		if(last.count(d)) insert(1,1,n,last[d].first,i-1,last[d].second);
	}
	for(pair<long long,pair<int,int>> x:last)
		d=x.first,insert(1,1,n,x.second.first,n,x.second.second);
	solve(1,1,n);
	return 0;
}

詳細信息

Test #1:

score: 4.54545
Accepted
time: 2ms
memory: 13072kb

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: 2ms
memory: 13096kb

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: 81ms
memory: 33144kb

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: '156835875'

Test #4:

score: 0
Wrong Answer
time: 2642ms
memory: 173672kb

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
250000105
375000147
210
875000294
378
375000483
595
875000728
861
375001015
1176
875001358
1540
375001743
1953
875002184
2415
375002667
2926
875003206
3486
375003787
4095
875004424
4753
375005103
5460
875005838
6216
375006615
7021
875007448
7875
375008323
8778
875009254...

result:

wrong answer 4th numbers differ - expected: '500000168', found: '250000105'

Test #5:

score: 0
Wrong Answer
time: 3726ms
memory: 177076kb

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:

375199611
750399194
375199632
91
375000147
210
875000294
378
375000483
595
875000728
861
375001015
1176
875001358
1540
375001743
1953
875002184
2415
375002667
2926
875003206
3486
375003787
4095
875004424
4753
375005103
5460
875005838
6216
375006615
7021
875007448
7875
375008323
8778
875009254
9730
3...

result:

wrong answer 1st numbers differ - expected: '376399979', found: '375199611'

Test #6:

score: 0
Memory Limit Exceeded

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:

810896481
453369594
165010026
418534028
974249270
919160479
252830459
787833825
169582432
805384142
816191854
534884724
42419948
742943289
372201240
986496665
935347590
962378785
83354144
333818930
386293847
858500899
984861931
41031925
94291954
813385834
159766025
239574725
817708947
559609527
2194...

result:


Test #7:

score: 0
Memory Limit Exceeded

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:

230568727
157921619
517988037
458267767
182193354
43483842
328692610
291270773
532571156
745011320
898611266
424823896
990476970
966333049
143323086
998509072
674187848
314573466
16658736
88794836
232646801
698198990
416395579
596960794
985876427
924317040
691222485
65279809
666815460
826635050
2499...

result:


Test #8:

score: 0
Memory Limit Exceeded

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:

389859778
70682807
8216065
640189594
297047903
112101119
80970408
857405860
798753376
121082641
134736236
265351359
870223089
330312583
934476249
9107824
123581618
217148988
288688413
375511950
166350784
753619183
404280056
711754575
203930573
347797820
127797765
510390101
126285865
469810906
883158...

result:


Test #9:

score: 0
Memory Limit Exceeded

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:

857652554
197215190
574691568
771068634
214294900
135596048
481561172
889153083
900307379
632309770
52078678
965794832
829227050
317145409
651228126
316682626
709850505
628871866
905336807
981020884
11002772
334276842
115167307
539473774
755126969
878189005
68664055
629817566
291463905
834659740
150...

result:


Test #10:

score: 0
Memory Limit Exceeded

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:

794730338
48798368
34980638
281004948
474305328
24178464
806932967
230818564
358397254
62762252
730786097
772575222
311756614
604758177
934504562
985481329
77351275
554468806
622552609
108749306
21393527
819604202
618555805
26680099
456481281
849662240
301285803
948499688
559136892
466442635
2230302...

result:


Test #11:

score: 0
Memory Limit Exceeded

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:

520560708
780423114
624451398
197775880
96472416
441033106
480717682
72844023
734976170
321987386
620526633
238214967
529820232
118446311
337613928
591485009
62723126
757974069
364245878
101553125
550737118
45276146
923215713
524945012
284604676
768635066
253401028
761042163
680755115
45674964
45806...

result:


Test #12:

score: 0
Memory Limit Exceeded

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:

479285491
185595437
328917168
615795470
466485744
678397429
292163657
12785698
941443905
362691250
813113967
78265616
213377329
294805271
188727022
443049638
707156863
285801948
363470347
610355373
265840793
609099004
497324273
507406182
839884376
93054699
355277531
228835554
933726383
712926679
810...

result:


Test #13:

score: 0
Memory Limit Exceeded

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:

330651739
93323796
193968875
205548953
636375670
767119348
144242283
334055178
379309206
831759935
274779359
863684448
911027239
885202453
534459930
607237343
206806715
529288729
582758510
867288093
820629232
743802845
767772111
282953769
588545817
725292060
925697645
239725162
353967375
410808505
5...

result:


Test #14:

score: 0
Wrong Answer
time: 2599ms
memory: 87076kb

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:

870831905
935481498
903222317
903222338
870963206
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61...

result:

wrong answer 1st numbers differ - expected: '700388007', found: '870831905'

Test #15:

score: 0
Wrong Answer
time: 2561ms
memory: 87024kb

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:

21
91
210
378
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
63546
66066
68635
71253
7392...

result:

wrong answer 1st numbers differ - expected: '656243188', found: '21'

Test #16:

score: 0
Wrong Answer
time: 2634ms
memory: 87040kb

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:

21
91
210
378
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
63546
66066
68635
71253
7392...

result:

wrong answer 1st numbers differ - expected: '123004833', found: '21'

Test #17:

score: 0
Wrong Answer
time: 2560ms
memory: 87092kb

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:

21
91
210
378
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
63546
66066
68635
71253
7392...

result:

wrong answer 1st numbers differ - expected: '809311757', found: '21'

Test #18:

score: 0
Wrong Answer
time: 2565ms
memory: 87140kb

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:

21
91
210
378
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
63546
66066
68635
71253
7392...

result:

wrong answer 1st numbers differ - expected: '530050851', found: '21'

Test #19:

score: 0
Wrong Answer
time: 2561ms
memory: 87116kb

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:

21
91
210
378
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
63546
66066
68635
71253
7392...

result:

wrong answer 1st numbers differ - expected: '128224308', found: '21'

Test #20:

score: 0
Wrong Answer
time: 2566ms
memory: 87012kb

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:

48656386
144053293
216080013
288106782
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
635...

result:

wrong answer 1st numbers differ - expected: '961356073', found: '48656386'

Test #21:

score: 0
Wrong Answer
time: 2594ms
memory: 87092kb

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:

346138775
346138796
210
378
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
63546
66066
68...

result:

wrong answer 1st numbers differ - expected: '92516536', found: '346138775'

Test #22:

score: 0
Wrong Answer
time: 2661ms
memory: 86964kb

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:

21
91
210
378
595
861
1176
1540
1953
2415
2926
3486
4095
4753
5460
6216
7021
7875
8778
9730
10731
11781
12880
14028
15225
16471
17766
19110
20503
21945
23436
24976
26565
28203
29890
31626
33411
35245
37128
39060
41041
43071
45150
47278
49455
51681
53956
56280
58653
61075
63546
66066
68635
71253
7392...

result:

wrong answer 1st numbers differ - expected: '733458470', found: '21'