QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#126550#4193. Joined SessionszhichengWA 70ms9300kbC++142.0kb2023-07-18 16:56:302023-07-18 16:56:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 16:56:32]
  • 评测
  • 测评结果:WA
  • 用时:70ms
  • 内存:9300kb
  • [2023-07-18 16:56:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int p[200010],las[100010],con[100010],s[400010],dp[100010][4];
struct s{
	int l,r;
	bool operator<(s a){
		if(l!=a.l){
			return l<a.l;
		}
		return r<a.r;
	}
}a[100010];
int m(int x,int y,int p){
	if(p==1){
		return max(x,y);
	}
	return min(x,y);
}
void update(int x,int y,int l,int r,int rt,int w){
	int mid=(l+r)>>1;
	if(l==r){
		s[rt]=m(s[rt],y,w);
		return;
	}
	if(x<=mid){
		update(x,y,l,mid,rt<<1,w);
	}
	else{
		update(x,y,mid+1,r,rt<<1|1,w);
	}
	s[rt]=m(s[rt<<1],s[rt<<1|1],w);
}
int query(int x,int y,int l,int r,int rt,int w){
	int mid=(l+r)>>1,ans=w?0:1e9;
	if(x<=l&&y>=r){
		return s[rt];
	}
	if(x<=mid){
		ans=m(ans,query(x,y,l,mid,rt<<1,w),w);
	}
	if(y>=mid+1){
		ans=m(ans,query(x,y,mid+1,r,rt<<1|1,w),w);
	}
	return ans;
}
int main(){
	int n,w=0,tot=0,pos;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].l,&a[i].r);
		p[++tot]=a[i].l;
		p[++tot]=a[i].r;
	}
	sort(a+1,a+n+1);
	sort(p+1,p+tot+1);
	tot=unique(p+1,p+tot+1)-p-1;
	for(int i=1;i<=n;i++){
		a[i].l=lower_bound(p+1,p+tot+1,a[i].l)-p;
		a[i].r=lower_bound(p+1,p+tot+1,a[i].r)-p;
		if(a[i].l<=a[i-1].r){
			w=1;
		}
	}
	if(!w){
		printf("impossible");
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(a[i].l!=1){
			las[i]=query(1,a[i].l-1,1,tot,1,1);
		}
		update(a[i].r,i,1,tot,1,1);
	}
	for(int i=1;i<=4*tot;i++){
		s[i]=n+1;
	}
	for(int i=1;i<=n;i++){
		con[i]=query(a[i].l,tot,1,tot,1,0);
		update(a[i].r,i,1,tot,1,0);
		if(con[i]==n+1){
			con[i]=i;
		}
	}
	memset(dp,127,sizeof(dp));
	for(int j=0;j<=3;j++){
		for(int i=1;i<=n;i++){
			if(!las[i]){
				dp[i][j]=1;
			}
			else{
				pos=i;
				for(int k=0;k<=j;k++){
					pos=con[pos];
					if(!las[pos]){
						dp[i][j]=1;
						break;
					}
					dp[i][j]=min(dp[i][j],dp[las[pos]][j-k]+1);
				}
			}
		}
	}
	for(int i=1;i<=3;i++){
		if(dp[n][i]<dp[n][0]){
			printf("%d",i);
			return 0;
		}
	}
	printf("impossible");
}

詳細信息

Test #1:

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

input:

4
1 3
2 5
4 7
6 9

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 2ms
memory: 5216kb

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

input:

3
1 2
2 3
3 4

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0
Accepted
time: 2ms
memory: 7340kb

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: 1ms
memory: 7368kb

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: 5184kb

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: 1ms
memory: 3548kb

input:

2
1 2
5 6

output:

impossible

result:

ok single line: 'impossible'

Test #8:

score: 0
Accepted
time: 2ms
memory: 5088kb

input:

2
1 3
2 4

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 2ms
memory: 7200kb

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: 0ms
memory: 5404kb

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: 7456kb

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

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: 1ms
memory: 5172kb

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: 3ms
memory: 7372kb

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: 5428kb

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

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: 40ms
memory: 7752kb

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: 41ms
memory: 9184kb

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

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: 7156kb

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

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

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

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: 5160kb

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: 3ms
memory: 5480kb

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: 45ms
memory: 7672kb

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: 44ms
memory: 9300kb

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: 49ms
memory: 8144kb

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: 55ms
memory: 7732kb

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: 53ms
memory: 8636kb

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: 57ms
memory: 9064kb

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: 58ms
memory: 8496kb

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: -100
Wrong Answer
time: 70ms
memory: 9232kb

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:

impossible

result:

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