QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431298#4193. Joined Sessionskevinyang#WA 197ms46512kbC++144.0kb2024-06-05 10:52:312024-06-05 10:52:31

Judging History

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

  • [2024-06-05 10:52:31]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:46512kb
  • [2024-06-05 10:52:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
struct SegTree{
	int size;
	vector<pii>arr;
	void init(int n){
		size = 1;
		while(size<n)size*=2;
		arr.resize(2*size);
	}
	void set(int i, pii v, int x, int lx, int rx){
		if(rx-lx==1){
			arr[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		if(i<m){
			set(i,v,2*x+1,lx,m);
		}
		else{
			set(i,v,2*x+2,m,rx);
		}
		arr[x] = min(arr[2*x+1],arr[2*x+2]);
	}
	void set(int i,pii v){
		set(i,v,0,0,size);
	}
	pii query(int l,int r, int x, int lx, int rx){
		if(lx>=r||l>=rx)return {(int)1e9+7,0LL};
		if(lx>=l&&rx<=r)return arr[x];
		int m = (lx+rx)/2;
		pii s1 = query(l,r,2*x+1,lx,m);
		pii s2 = query(l,r,2*x+2,m,rx);
		return min(s1,s2);
	}
	pii query(int l, int r){
		return query(l,r,0,0,size);
	}
};
struct SegTree2{
	int size;
	vector<pii>arr;
	void init(int n){
		size = 1;
		while(size<n)size*=2;
		arr.resize(2*size);
	}
	void set(int i, pii v, int x, int lx, int rx){
		if(rx-lx==1){
			arr[x] = v;
			return;
		}
		int m = (lx+rx)/2;
		if(i<m){
			set(i,v,2*x+1,lx,m);
		}
		else{
			set(i,v,2*x+2,m,rx);
		}
		arr[x] = max(arr[2*x+1],arr[2*x+2]);
	}
	void set(int i,pii v){
		set(i,v,0,0,size);
	}
	pii query(int l,int r, int x, int lx, int rx){
		if(lx>=r||l>=rx)return {0LL,0LL};
		if(lx>=l&&rx<=r)return arr[x];
		int m = (lx+rx)/2;
		pii s1 = query(l,r,2*x+1,lx,m);
		pii s2 = query(l,r,2*x+2,m,rx);
		return max(s1,s2);
	}
	pii query(int l, int r){
		return query(l,r,0,0,size);
	}
};
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int>l(n+1);
	vector<int>r(n+1);
	vector<int>sorted;
	for(int i = 1; i<=n; i++){
		cin >> l[i] >> r[i];
		sorted.push_back(l[i]);
		sorted.push_back(r[i]);
	}
	sorted.push_back(-69);
	sort(sorted.begin(),sorted.end());
	for(int i = 1; i<=n; i++){
		l[i] = lower_bound(sorted.begin(),sorted.end(),l[i])-sorted.begin();
		r[i] = lower_bound(sorted.begin(),sorted.end(),r[i])-sorted.begin();
	}
	SegTree left;
	SegTree2 right;
	left.init(2*n+5);
	right.init(2*n+5);
	vector<pii>lt(2*n+1,{(int)1e9,(int)1e9});
	vector<pii>rt(2*n+1);
	vector<vector<int>>lts(2*n+1);
	vector<vector<int>>rts(2*n+1);
	for(int i = 1; i<=n; i++){
		lt[r[i]] = min(lt[r[i]],{l[i],i});
		rt[l[i]] = max(rt[l[i]],{r[i],i});
		lts[r[i]].push_back(l[i]);
		rts[l[i]].push_back(r[i]);
	}
	for(int i = 1; i<=2*n; i++){
		right.set(i,rt[i]);
		left.set(i,lt[i]);
	}
	vector<int>dpl(2*n+5);
	vector<int>dpr(2*n+5);
	{
		int far = 0;
		for(int i = 1; i<=2*n; i++){
			if(lt[i] == make_pair((int)1e9,(int)1e9)){
				dpl[i] = dpl[i-1];
				continue;
			}
			else{
				for(int nxt: lts[i]){
					far = max(far,nxt);
				}
			}
			auto p = left.query(far,i+1);
			dpl[i] = dpl[p.first-1]+1;
		}
	}
	{
		int far = 2*n+1;
		for(int i = 2*n; i>=1; i--){
			if(rt[i] == make_pair(0,0)){
				dpr[i] = dpr[i+1];
				continue;
			}
			else{
				for(int nxt: rts[i]){
					far = min(far,nxt);
				}
			}
			auto p = right.query(i,far+1);
			dpr[i] = dpr[p.first+1]+1;
		}
	}
	int best = dpl[2*n];
	const int ln = 24;
	vector<vector<int>>dp(n+1,vector<int>(ln));
	for(int i = 1; i<=n; i++){
		auto p = right.query(l[i],r[i]+1);
		dp[i][0] = p.second;
	}
	for(int j = 1; j<ln; j++){
		for(int i = 1; i<=n; i++){
			dp[i][j] = dp[dp[i][j-1]][j-1];
		}
	}
	// cout << '\n';
	// for(int i = 1; i<=n; i++){
	// 	cout << l[i] << ' ' << r[i] << '\n';
	// }
	// for(int i = 1; i<=2*n; i++){
	// 	cout << dpl[i] << ' ' ;
	// }
	// cout << '\n';
	// for(int i = 1; i<=2*n; i++){
	// 	cout << dpr[i] << ' ' ;
	// }
	// cout << '\n';
	int ans = (int)1e9;
	for(int i = 1; i<=n; i++){
		int ret = 0;
		int u = i;
		for(int j = ln-1; j>=0; j--){
			int nu = dp[u][j];
			if(1 + dpl[l[i]-1] + dpr[r[nu]+1] < best){
				continue;
			}
			u = nu;
			ret+=1<<j;
		}
		if(ret < (1<<22)){
			ans = min(ans,ret+1);
		}
	}
	if(ans==(int)1e9){
		cout << "impossible\n";
		return 0;
	}
	cout << ans << '\n';
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3596kb

input:

4
1 3
2 5
4 7
6 9

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

5
1 3
4 7
8 10
2 5
6 9

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

3
1 2
2 3
3 4

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

6
1 3
2 5
4 7
6 9
8 11
10 12

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

5
1 2
2 3
3 4
5 6
6 7

output:

impossible

result:

ok single line: 'impossible'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

2
1 2
5 6

output:

impossible

result:

ok single line: 'impossible'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2
1 3
2 4

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3572kb

input:

5
3 5
2 7
1 10
6 8
9 11

output:

impossible

result:

ok single line: 'impossible'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

10
229 315
444 459
459 828
232 324
350 371
208 235
371 430
430 456
324 350
172 208

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

15
227 313
471 486
487 522
230 322
377 398
206 233
398 457
457 483
322 348
102 138
138 206
348 377
476 506
522 885
67 102

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

20
261 347
505 520
521 556
264 356
411 432
240 267
432 491
491 517
356 382
136 172
172 240
382 411
510 540
556 579
67 102
579 931
22 80
69 136
271 327
11 53

output:

2

result:

ok single line: '2'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

50
383 469
703 718
719 754
386 478
584 605
362 389
619 678
689 715
498 524
172 208
211 279
524 553
708 738
788 811
67 102
855 857
22 80
69 136
393 449
11 53
229 302
421 440
710 747
198 222
315 385
413 439
91 171
882 1029
788 858
922 1077
305 330
84 111
336 341
772 801
313 370
124 219
539 584
740 807...

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3516kb

input:

100
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279
567 596
782 812
862 885
67 102
929 931
22 80
69 136
393 449
11 53
229 302
421 440
784 821
198 222
315 385
413 439
91 171
956 1029
862 932
996 1077
305 330
84 111
336 341
846 875
313 370
124 219
582 627
814 88...

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

500
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279
567 596
782 812
862 885
67 102
929 931
22 80
69 136
393 449
11 53
229 302
421 440
784 821
198 222
315 385
413 439
91 171
956 1029
862 932
996 1077
305 330
84 111
336 341
846 875
313 370
124 219
582 627
814 88...

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 13ms
memory: 7216kb

input:

9999
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279
567 596
782 812
862 885
67 102
929 931
22 80
69 136
393 449
11 53
229 302
421 440
784 821
198 222
315 385
413 439
91 171
956 1029
862 932
996 1077
305 330
84 111
336 341
846 875
313 370
124 219
582 627
814 8...

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 113ms
memory: 41260kb

input:

99998
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279
567 596
782 812
862 885
67 102
929 931
22 80
69 136
393 449
11 53
229 302
421 440
784 821
198 222
315 385
413 439
91 171
956 1029
862 932
996 1077
305 330
84 111
336 341
846 875
313 370
124 219
582 627
814 ...

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 119ms
memory: 41272kb

input:

99999
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279
567 596
782 812
862 885
67 102
929 931
22 80
69 136
393 449
11 53
229 302
421 440
784 821
198 222
315 385
413 439
91 171
956 1029
862 932
996 1077
305 330
84 111
336 341
846 875
313 370
124 219
582 627
814 ...

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3728kb

input:

11
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279

output:

impossible

result:

ok single line: 'impossible'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

16
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279
567 596
782 812
862 885
67 102
929 931

output:

impossible

result:

ok single line: 'impossible'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

21
383 469
777 792
793 828
386 478
649 670
362 389
690 749
763 789
540 566
172 208
211 279
567 596
782 812
862 885
67 102
929 931
22 80
69 136
393 449
11 53
229 302

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

51
766 852
1554 1569
1586 1621
772 864
1298 1319
724 751
1380 1439
1526 1552
1080 1106
344 380
422 490
1134 1163
1564 1594
1724 1747
134 169
1858 1860
44 102
138 205
786 842
22 64
458 531
842 861
1568 1605
396 420
630 700
826 852
182 262
1912 1985
1724 1794
1992 2073
610 635
168 195
672 677
1692 172...

output:

1

result:

ok single line: '1'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

110
766 852
1554 1569
1586 1621
772 864
1298 1319
724 751
1380 1439
1526 1552
1080 1106
344 380
422 490
1134 1163
1564 1594
1724 1747
134 169
1858 1860
44 102
138 205
786 842
22 64
458 531
842 861
1568 1605
396 420
630 700
826 852
182 262
1912 1985
1724 1794
1992 2073
610 635
168 195
672 677
1692 17...

output:

1

result:

ok single line: '1'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

501
766 852
1554 1569
1586 1621
772 864
1298 1319
724 751
1380 1439
1526 1552
1080 1106
344 380
422 490
1134 1163
1564 1594
1724 1747
134 169
1858 1860
44 102
138 205
786 842
22 64
458 531
842 861
1568 1605
396 420
630 700
826 852
182 262
1912 1985
1724 1794
1992 2073
610 635
168 195
672 677
1692 17...

output:

1

result:

ok single line: '1'

Test #25:

score: 0
Accepted
time: 6ms
memory: 7160kb

input:

9999
766 852
1554 1569
1586 1621
772 864
1298 1319
724 751
1380 1439
1526 1552
1080 1106
344 380
422 490
1134 1163
1564 1594
1724 1747
134 169
1858 1860
44 102
138 205
786 842
22 64
458 531
842 861
1568 1605
396 420
630 700
826 852
182 262
1912 1985
1724 1794
1992 2073
610 635
168 195
672 677
1692 1...

output:

1

result:

ok single line: '1'

Test #26:

score: 0
Accepted
time: 118ms
memory: 41404kb

input:

99998
766 852
1554 1569
1586 1621
772 864
1298 1319
724 751
1380 1439
1526 1552
1080 1106
344 380
422 490
1134 1163
1564 1594
1724 1747
134 169
1858 1860
44 102
138 205
786 842
22 64
458 531
842 861
1568 1605
396 420
630 700
826 852
182 262
1912 1985
1724 1794
1992 2073
610 635
168 195
672 677
1692 ...

output:

1

result:

ok single line: '1'

Test #27:

score: 0
Accepted
time: 114ms
memory: 41352kb

input:

99999
766 852
1554 1569
1586 1621
772 864
1298 1319
724 751
1380 1439
1526 1552
1080 1106
344 380
422 490
1134 1163
1564 1594
1724 1747
134 169
1858 1860
44 102
138 205
786 842
22 64
458 531
842 861
1568 1605
396 420
630 700
826 852
182 262
1912 1985
1724 1794
1992 2073
610 635
168 195
672 677
1692 ...

output:

1

result:

ok single line: '1'

Test #28:

score: 0
Accepted
time: 125ms
memory: 41552kb

input:

99998
3830 3916
7770 7785
7930 7965
3860 3952
6490 6511
3620 3647
6900 6959
7630 7656
5400 5426
1720 1756
2110 2178
5670 5699
7820 7850
8620 8643
670 705
9290 9292
220 278
690 757
3930 3986
110 152
2290 2363
4210 4229
7840 7877
1980 2004
3150 3220
4130 4156
910 990
9560 9633
8620 8690
9960 10041
305...

output:

2

result:

ok single line: '2'

Test #29:

score: 0
Accepted
time: 119ms
memory: 41640kb

input:

99999
3830 3916
7770 7785
7930 7965
3860 3952
6490 6511
3620 3647
6900 6959
7630 7656
5400 5426
1720 1756
2110 2178
5670 5699
7820 7850
8620 8643
670 705
9290 9292
220 278
690 757
3930 3986
110 152
2290 2363
4210 4229
7840 7877
1980 2004
3150 3220
4130 4156
910 990
9560 9633
8620 8690
9960 10041
305...

output:

2

result:

ok single line: '2'

Test #30:

score: 0
Accepted
time: 139ms
memory: 42856kb

input:

99998
38300 38386
77700 77715
79300 79335
38600 38692
64900 64921
36200 36227
69000 69059
76300 76326
54000 54026
17200 17236
21100 21168
56700 56729
78200 78230
86200 86223
6700 6735
92900 92902
2200 2258
6900 6967
39300 39356
1100 1142
22900 22973
42100 42119
78400 78437
19800 19824
31500 31570
41...

output:

impossible

result:

ok single line: 'impossible'

Test #31:

score: 0
Accepted
time: 138ms
memory: 42804kb

input:

99999
38300 38386
77700 77715
79300 79335
38600 38692
64900 64921
36200 36227
69000 69059
76300 76326
54000 54026
17200 17236
21100 21168
56700 56729
78200 78230
86200 86223
6700 6735
92900 92902
2200 2258
6900 6967
39300 39356
1100 1142
22900 22973
42100 42119
78400 78437
19800 19824
31500 31570
41...

output:

impossible

result:

ok single line: 'impossible'

Test #32:

score: 0
Accepted
time: 145ms
memory: 42780kb

input:

99999
383000 383086
777000 777015
793000 793035
386000 386092
649000 649021
362000 362027
690000 690059
763000 763026
540000 540026
172000 172036
211000 211068
567000 567029
782000 782030
862000 862023
67000 67035
929000 929002
22000 22058
69000 69067
393000 393056
11000 11042
229000 229073
421000 4...

output:

impossible

result:

ok single line: 'impossible'

Test #33:

score: 0
Accepted
time: 182ms
memory: 46388kb

input:

99999
105683616 105692651
18111183 18114306
227651066 227657778
841261986 841276865
186689275 186699114
920321111 920342987
696518226 696523266
329159419 329169520
657138825 657162765
215002000 215018692
20317046 20329211
450700082 450717450
626431634 626445442
871848028 871877725
729687583 72969276...

output:

3

result:

ok single line: '3'

Test #34:

score: 0
Accepted
time: 191ms
memory: 46348kb

input:

99999
621671866 621689355
260637225 260671451
369704836 369710724
725685662 725710508
22428571 22443369
642856993 642885299
698285582 698312712
120410361 120429207
167592012 167604340
205374731 205394706
365617680 365643193
860995202 861000055
267302066 267326200
238978436 238990560
84846707 8485401...

output:

3

result:

ok single line: '3'

Test #35:

score: 0
Accepted
time: 195ms
memory: 46380kb

input:

99999
453457655 453479336
744967415 744983991
599539613 599552610
804296688 804307342
731746013 731888389
797264655 797287818
942438092 942462518
893112015 893173067
569467815 569471608
717411287 717431783
802785379 802841071
531883863 531911803
342147899 342185849
352838933 352859499
224245637 2242...

output:

3

result:

ok single line: '3'

Test #36:

score: 0
Accepted
time: 182ms
memory: 46512kb

input:

99999
175386704 175599566
358283198 358366127
18806211 19163132
394562342 394681629
925603355 926365928
40371148 40478709
523681777 524107404
226575947 226898929
356770293 356928466
600146546 600195586
586576969 586868047
521564139 521908893
324325487 324557830
68538995 68743149
24642808 24759034
65...

output:

3

result:

ok single line: '3'

Test #37:

score: 0
Accepted
time: 197ms
memory: 46348kb

input:

99999
898578216 898756004
118732762 119481878
450467503 451253718
497745704 498721863
871077176 871082620
999580163 999720990
695992163 696856126
887875007 888927751
329075031 330721148
843572572 845458018
732416852 733368564
741413694 743170711
972825337 973493710
851863955 852268984
77241841 77479...

output:

3

result:

ok single line: '3'

Test #38:

score: 0
Accepted
time: 164ms
memory: 46412kb

input:

99999
762130104 762133110
29274639 29283121
13583407 13597071
841205062 841216772
608178029 608184133
920248306 920256470
696459412 696479453
329061045 329068465
430361122 430367982
178535270 178544839
40471992 40480261
584659324 584674991
21259564 21268129
871786431 871797215
729544725 729562836
75...

output:

2

result:

ok single line: '2'

Test #39:

score: -100
Wrong Answer
time: 175ms
memory: 46316kb

input:

99999
521888913 521896003
260045736 260057508
852458694 852483860
725300193 725333541
764288966 764299433
333323692 333364521
701246937 701262245
120295408 120316480
638996373 639001386
652473287 652496025
25181905 25198304
861499720 861511451
266569934 266578928
739253304 739257931
492628921 492632...

output:

3

result:

wrong answer 1st lines differ - expected: '2', found: '3'