QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608111#9427. Collect the Coins2497201210TL 635ms66112kbC++201.7kb2024-10-03 18:34:442024-11-06 16:01:45

Judging History

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

  • [2024-11-06 16:01:45]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:TL
  • 用时:635ms
  • 内存:66112kb
  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-03 18:34:45]
  • 评测
  • 测评结果:100
  • 用时:685ms
  • 内存:66192kb
  • [2024-10-03 18:34:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e6+10;
const int P=1e9+7;

pair<int,vector<int>>md[N];
int idx=0;
bool check(int x) {
	int l=-1e10;int r=1e10;
	int d;
	if(md[1].second.size()==1){
		d=md[1].second[0];
	}
	else {
		d=md[1].second[0];
		l=r=md[1].second[1];
	}
	for(int i=2;i<=idx;i++){
		int cha=md[i].first-md[i-1].first;
		cha=cha*x;
		l-=cha;r+=cha;
		if(md[i].second.size()==2){
			int pos1=md[i].second[0];int pos2=md[i].second[1];
			if(pos1>=d-cha&&pos1<=d+cha&&pos2>=l&&pos2<=r){
				d=pos1;
				l=r=pos2;
			}
			else if(pos2>=d-cha&&pos2<=d+cha&&pos1>=l&&pos1<=r){
				d=pos1;
				l=r=pos2;
			}
			else{
				return 0;
			}
		}
		else{
			int pos=md[i].second[0];
			if(pos>=l&&pos<=r&&pos>=d-cha&&pos<=d+cha){
				
				l=min(l,d-cha);
				r=max(r,d+cha);d=pos;
			}
			else{
				if(pos>=l&&pos<=r){
					l=d-cha;
					r=d+cha;
					d=pos;
				}
				else if(pos>=d-cha&&pos<=d+cha){
					d=pos;
				}
				else{
					return 0;
				}
			}
		}
	}
	return 1;
}
inline void solve() {
	int n;
	cin>>n;
	bool f=1;idx=0;
	for(int i=1; i<=n; i++) {
		int a,b;
		cin>>a>>b;
		if(idx==0||md[idx].first!=a){
			md[++idx].first=a;
			md[idx].second.resize(0);
			md[idx].second.push_back(b);
		}
		else{
			md[idx].second.push_back(b);
		}
		if(md[idx].second.size()>2)f=0;
	}
	if(f) {
		
		int l=0;
		int r=1e9+100;
		while(l<r) {
			int mid=l+r>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		cout<<l<<endl;
	} else {
		cout<<-1<<endl;
	}
}
signed main() {

	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	cin>>t;
	while(t--) {
		solve();
	}
}


詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3524kb

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 44ms
memory: 4304kb

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:

0
3
0
3
1
3
6
0
3
2
2
0
2
5
0
1
5
1
2
0
0
0
1
4
2
0
2
1
3
0
3
2
3
2
5
3
1
1
0
1
1
1
0
2
0
1
0
1
0
2
1
0
2
3
4
4
1
1
1
0
1
3
0
1
4
4
3
0
0
2
2
6
4
2
1
0
0
1
0
2
1
2
0
1
1
3
0
0
1
2
0
3
0
2
2
2
1
0
0
0
5
1
2
0
6
1
1
1
2
2
2
0
3
1
4
3
6
0
8
1
1
3
0
2
2
4
1
1
0
0
0
7
2
2
1
0
0
3
1
2
1
1
2
5
3
0
3
3
3
5
...

result:

ok 1135 lines

Test #3:

score: 0
Accepted
time: 494ms
memory: 46536kb

input:

1
1000000
2 57841
2 357142
3 496329
3 545446
4 503408
4 590762
5 78281
6 196926
6 349414
7 200245
8 953412
11 616898
12 592065
13 945945
15 20908
15 852722
16 221184
16 401521
17 884478
18 186072
18 931445
19 833560
20 314177
21 138453
21 731965
22 172104
23 595921
25 372617
27 545759
28 977029
30 4...

output:

994024

result:

ok single line: '994024'

Test #4:

score: 0
Accepted
time: 470ms
memory: 63404kb

input:

1
1000000
6 1991827
13 8125243
19 22493
24 4282711
28 356362
39 765152
41 6737899
44 8549464
57 4530192
64 7201376
67 6695629
70 3830504
70 6658581
71 4591382
71 8349070
75 2107828
76 4073563
81 2712838
92 1391185
95 4663781
102 5986957
113 8423636
118 7826607
122 1171556
122 3118750
160 938066
162 ...

output:

9609125

result:

ok single line: '9609125'

Test #5:

score: 0
Accepted
time: 570ms
memory: 66088kb

input:

1
1000000
108 565196036
597 561009880
1007 831705109
2597 55966094
2869 765993518
3025 202191673
3283 237167825
3410 829643653
4879 960747182
7284 679152790
8765 64201585
8899 97619554
9320 713144607
9519 991746776
9913 346063307
11161 970513525
11256 975123550
12073 778562963
14286 206857559
15803 ...

output:

268764694

result:

ok single line: '268764694'

Test #6:

score: 0
Accepted
time: 44ms
memory: 4228kb

input:

1135
9
1 7
3 7
4 10
5 2
6 8
7 10
8 3
9 10
10 4
9
1 4
3 2
4 1
5 3
5 7
7 2
8 4
10 7
10 10
5
3 10
4 4
7 3
8 8
9 7
8
4 1
4 4
5 5
6 4
8 3
8 4
9 2
9 4
3
1 4
5 3
10 9
7
2 6
3 4
4 2
6 3
6 9
8 3
8 7
7
1 5
3 6
4 8
4 9
5 10
8 4
8 10
1
8 6
9
1 6
2 6
3 9
5 9
6 7
6 9
8 1
9 4
10 4
5
3 9
4 3
4 6
6 4
8 5
7
1 1
2 1
3...

output:

3
2
1
1
1
2
2
0
3
3
4
0
4
1
3
2
0
0
0
3
2
6
3
0
1
0
4
0
3
0
2
0
3
0
0
1
4
0
1
2
4
0
2
1
1
1
2
8
1
1
1
1
1
5
0
1
0
3
0
3
2
2
3
2
5
0
0
2
6
4
3
2
2
1
2
0
0
4
5
0
6
5
0
4
3
5
4
1
3
0
0
2
0
8
2
1
1
2
1
3
1
1
4
0
5
0
4
0
1
6
0
7
1
1
0
3
2
1
5
1
3
1
1
8
3
0
2
1
1
0
0
1
1
1
0
6
1
1
1
1
0
0
1
3
1
4
0
2
0
1
...

result:

ok 1135 lines

Test #7:

score: 0
Accepted
time: 502ms
memory: 66024kb

input:

1
1000000
1 421151
2 313604
3 982622
4 993745
5 997253
6 859839
7 835793
8 324554
9 553026
10 218950
11 672201
12 373214
13 147841
14 445973
15 807912
16 753995
17 564224
18 662086
19 862430
20 378806
21 591406
22 415543
23 490080
24 184083
25 287323
26 578004
27 302543
28 302371
29 689597
30 538475...

output:

492642

result:

ok single line: '492642'

Test #8:

score: 0
Accepted
time: 504ms
memory: 66104kb

input:

1
1000000
4 5761079
27 9913703
31 3480982
33 8607438
37 3321663
64 3998110
72 4273261
78 7438482
84 8988669
96 920933
101 9309679
106 2230436
118 8605436
123 104422
129 7742745
131 4597839
139 9509656
142 3293909
159 9386630
176 9018043
188 3538661
207 9103530
233 2796496
239 7390510
246 2350961
249...

output:

4801594

result:

ok single line: '4801594'

Test #9:

score: 0
Accepted
time: 588ms
memory: 66024kb

input:

1
1000000
1659 745509192
1793 453656007
2417 245865714
3481 181708105
4181 423236911
5279 477367945
7195 966897525
9086 169940320
12642 77818181
14303 26150912
15915 448404964
16486 168882999
16531 105802492
16723 521426994
16754 508715351
19350 563835961
20119 410674400
20775 157959337
20870 320155...

output:

257246803

result:

ok single line: '257246803'

Test #10:

score: 0
Accepted
time: 466ms
memory: 64368kb

input:

1
1000000
1 199948
2 400091
2 463093
3 30523
4 771947
6 320897
7 104702
8 993244
9 926737
10 794612
11 210817
12 351420
13 495204
14 86010
16 589773
17 940494
18 467002
19 785066
20 724000
21 843646
22 47780
23 44610
24 494920
25 717543
27 869625
27 888906
28 972386
29 138651
30 73442
31 229124
32 4...

output:

983172

result:

ok single line: '983172'

Test #11:

score: 0
Accepted
time: 511ms
memory: 63720kb

input:

1
1000000
8 4343641
20 9188668
27 7784999
36 567704
71 225957
104 1690417
111 6719613
130 3931557
131 4091107
138 6733754
140 694514
143 5699446
164 8271151
190 5161164
204 6604398
219 7818039
225 103011
225 1033586
229 5290991
258 6252181
268 7412984
269 1107497
270 5043326
282 5968288
303 893538
3...

output:

9374697

result:

ok single line: '9374697'

Test #12:

score: 0
Accepted
time: 591ms
memory: 63364kb

input:

1
1000000
339 331918409
1828 806301739
4285 288684076
5821 210020913
6987 489751813
8084 346009704
9692 770088627
10407 404154547
10866 421926603
11062 935900735
11722 724947155
13636 832546152
16251 197187715
16251 291560397
17148 385272967
18475 77755669
19621 568102456
21145 20338367
21638 135488...

output:

907611400

result:

ok single line: '907611400'

Test #13:

score: 0
Accepted
time: 42ms
memory: 3860kb

input:

1135
10
1 3
1 7
2 3
2 5
4 7
4 8
6 1
6 4
7 5
7 8
8
1 4
2 2
2 3
3 5
3 10
6 8
9 1
9 4
1
10 7
1
2 5
6
1 6
1 9
5 2
5 9
8 1
8 4
6
5 8
5 9
6 5
6 10
8 3
8 9
9
1 5
1 6
4 9
5 6
5 7
7 2
7 10
10 2
10 3
3
6 9
10 5
10 8
3
4 6
4 7
7 10
1
8 6
7
1 2
2 3
2 10
3 4
3 6
5 4
5 9
3
2 1
2 9
7 7
8
6 2
6 8
7 6
7 7
8 2
8 3
10...

output:

4
7
0
0
2
3
3
1
1
0
4
1
4
1
0
1
0
7
1
2
1
3
3
1
4
4
0
0
2
0
2
5
0
3
1
3
2
4
0
0
4
2
0
6
5
2
1
3
0
1
2
0
2
2
2
2
0
1
4
5
0
6
5
5
0
0
2
0
2
3
1
5
5
4
3
6
0
2
3
7
1
0
0
0
1
1
4
2
5
4
0
0
3
3
0
0
1
0
3
1
2
5
3
2
3
5
0
1
3
7
4
3
3
0
2
0
0
1
1
3
3
1
0
0
3
1
0
0
6
3
6
7
1
0
0
4
4
0
0
1
4
2
3
2
1
6
0
0
2
0
...

result:

ok 1135 lines

Test #14:

score: 0
Accepted
time: 403ms
memory: 36588kb

input:

1
1000000
2 77901
2 299883
4 428639
4 813168
5 100173
5 782917
7 40384
7 449788
11 236799
11 975047
12 459959
12 627756
14 268070
14 838229
15 42307
15 750817
18 429714
18 542540
20 396104
20 555946
24 382023
24 670885
25 123347
25 160290
26 338330
26 462536
29 78983
29 370000
32 431681
32 899225
33...

output:

993613

result:

ok single line: '993613'

Test #15:

score: 0
Accepted
time: 456ms
memory: 35888kb

input:

1
1000000
4 3326080
4 9907237
39 453090
39 7480697
52 2672608
52 7499680
78 1255223
78 1706176
117 135598
117 161705
131 2847430
131 9067040
201 2370848
201 4954617
256 832631
256 4772412
265 2646914
265 9939501
291 995828
291 7583564
311 4996097
311 8685066
334 1025837
334 8498081
338 2244726
338 2...

output:

9776177

result:

ok single line: '9776177'

Test #16:

score: 0
Accepted
time: 515ms
memory: 36376kb

input:

1
1000000
1387 627417959
1387 938885698
2331 35605535
2331 388781199
2813 377765380
2813 717077893
11097 80601983
11097 601468694
18924 26066416
18924 371804579
21959 646680704
21959 676102593
27236 566499457
27236 811388411
30230 462184409
30230 972254978
30814 68498987
30814 655963890
33826 734512...

output:

804824864

result:

ok single line: '804824864'

Test #17:

score: 0
Accepted
time: 481ms
memory: 66016kb

input:

1
1000000
1 629518
2 558549
3 383006
4 699159
5 984135
6 611950
7 799380
8 832403
9 433826
10 32632
11 47592
12 326209
13 642377
14 571080
15 323890
16 516728
17 213474
18 184305
19 671257
20 790199
21 869443
22 2422
23 891767
24 970860
25 378958
26 423947
27 591026
28 924544
29 461837
30 766426
31 ...

output:

953927

result:

ok single line: '953927'

Test #18:

score: 0
Accepted
time: 635ms
memory: 66112kb

input:

1
1000000
1 2453219
5 7814367
16 6026787
36 3033808
44 2359233
58 5665018
71 2603810
82 206926
84 179910
87 7812418
90 2144755
91 6521845
99 3620108
103 7674842
107 9537913
122 999505
123 1633867
135 3788282
151 9382734
161 996636
184 2564772
196 7480123
211 433598
225 1033075
232 3331142
237 487546...

output:

7974809

result:

ok single line: '7974809'

Test #19:

score: -100
Time Limit Exceeded

input:

1
1000000
1792 157427572
2445 81759698
3012 507330494
4313 706991734
4587 974169736
4676 666835954
4840 292019582
5392 810147227
5419 942861921
6835 573293913
6953 577978485
8218 455854676
8754 581632453
9288 889057541
10396 668313073
11446 595224977
12789 977427415
13012 77119835
13083 565585658
13...

output:

230091421

result: