QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106239#6311. 火车站sichengzhou30 90ms10464kbC++141.3kb2023-05-17 01:28:142023-05-17 01:28:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-17 01:28:17]
  • 评测
  • 测评结果:30
  • 用时:90ms
  • 内存:10464kb
  • [2023-05-17 01:28:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,x;
int isl[N],isr[N];
int minl[N],maxr[N];
int t1[N<<2],t2[N<<2];
void build(int p,int l,int r)
{
	if(l==r)
	{
		t1[p]=n+1;t2[p]=0;
		return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
	{
		t1[p]=min(t1[p],x);
		t2[p]=max(t2[p],y);
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)
	{
		change(p<<1,l,mid,x,y); 
	}
	if(mid+1<=y)
	{
		change(p<<1|1,mid+1,r,x,y);
	}
}
void lazydown(int p,int l,int r)
{
	if(l==r)
	{
		minl[l]=t1[p];
		maxr[l]=t2[p];
		return ;
	}
	t1[p<<1]=min(t1[p<<1],t1[p]);
	t1[p<<1|1]=min(t1[p<<1|1],t1[p]);
	t2[p<<1]=max(t2[p<<1],t2[p]);
	t2[p<<1|1]=max(t2[p<<1|1],t2[p]);
	int mid=l+r>>1;
	lazydown(p<<1,l,mid);
	lazydown(p<<1|1,mid+1,r); 
}
int main()
{
	int x,y,z,L,R;
	scanf("%d%d%d",&n,&m,&z);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		change(1,1,n,x,y);
		isl[x]=1;
		isr[y]=1;
	}
	lazydown(1,1,n);
	L=z;
	for(int i=z;i>1;i--)
	{
		if(minl[i]>i-1)
		{
			break;
		}else{
			L=i-1;
		}
	}
	R=z;
	for(int i=z;i<n;i++)
	{
		if(maxr[i]<i+1)
		{
			break;
		}else{
			R=i+1; 
		}
	}
	for(int i=L;i<=R;i++)
	{
		if(i<z&&isl[i]||i>z&&isr[i])
		{
			printf("%d ",i);
		}
	}
	return 0;
}

详细

Test #1:

score: 10
Accepted
time: 2ms
memory: 3768kb

input:

46 50 24
38 39
14 18
38 41
38 40
38 44
1 9
20 32
2 31
6 23
4 11
38 40
38 40
24 30
10 32
1 15
13 30
7 29
3 7
15 36
17 30
5 9
38 44
38 46
22 29
2 25
4 32
38 44
38 45
33 36
1 20
38 41
38 40
9 20
23 26
38 40
29 31
8 23
2 6
1 24
10 29
38 42
38 42
38 40
38 44
5 8
38 45
10 20
14 34
9 33
16 28

output:

1 2 3 4 5 6 7 8 9 10 13 14 15 16 17 20 22 23 25 26 28 29 30 31 32 33 34 36 

result:

ok 28 numbers

Test #2:

score: 0
Wrong Answer
time: 2ms
memory: 3584kb

input:

46 49 22
25 28
5 14
24 29
43 46
13 14
5 14
9 14
12 14
24 33
18 33
3 14
17 40
26 32
1 14
43 46
33 36
4 14
43 44
20 21
2 14
25 30
23 28
43 45
43 46
29 38
43 45
3 14
9 14
11 14
13 14
33 38
25 41
9 14
3 14
1 14
3 14
43 46
30 38
10 14
3 14
9 14
31 33
17 38
6 14
6 14
10 14
5 14
11 14
17 20

output:

1 2 3 4 5 6 9 10 11 12 13 17 18 20 28 29 30 32 33 36 38 40 41 

result:

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

Test #3:

score: 0
Wrong Answer
time: 3ms
memory: 3732kb

input:

4901 4742 2784
1660 2698
1184 1582
3644 3650
860 1582
12 1582
4284 4750
693 1582
4284 4420
530 1582
4284 4778
213 1582
1346 1582
2456 3284
1951 2247
2526 3899
1748 3843
1840 4158
1847 3233
2710 4082
17 1582
1217 1582
2732 3868
2176 3652
1440 1582
3392 3778
115 1582
51 1582
4284 4410
343 1582
696 158...

output:

1 3 4 5 6 7 8 9 10 11 12 14 16 17 18 19 20 21 22 24 25 26 27 28 29 30 31 32 33 34 35 37 39 40 41 42 43 44 45 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 63 64 65 67 68 70 71 72 73 74 76 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 100 101 102 104 105 106 108 110 111 112 113 114 11...

result:

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

Test #4:

score: 0
Wrong Answer
time: 0ms
memory: 3956kb

input:

4752 4916 2637
631 1748
1958 2543
976 1748
4059 4176
1753 2555
1293 1748
400 1748
1531 1748
439 1748
814 1748
752 1748
4059 4745
1500 1748
410 1748
4059 4543
860 1748
3244 3846
1484 1748
2949 3200
365 1748
490 1748
533 1748
159 1748
2145 3211
938 1748
2104 2499
4059 4568
1321 1748
114 1748
257 1748
...

output:

2 3 4 5 7 8 9 10 11 12 13 14 15 16 18 19 20 21 23 24 25 27 28 29 30 31 32 33 35 36 37 38 39 40 41 42 43 45 46 47 48 49 50 51 52 54 55 56 57 58 59 60 62 63 64 65 66 67 69 70 71 72 73 74 75 76 77 78 79 81 82 83 84 85 86 87 88 89 91 92 93 94 95 96 97 102 103 104 106 107 108 109 110 111 112 113 114 116 ...

result:

wrong answer 1st numbers differ - expected: '1750', found: '2'

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 3812kb

input:

4638 4800 2174
763 2920
3689 3981
1696 1863
2225 3298
4041 4197
514 565
955 2677
982 1067
4041 4426
369 565
1280 1583
2033 2897
4041 4147
2216 3385
2470 3479
4041 4231
284 565
333 565
4041 4496
2471 3315
156 565
1449 2938
1754 3500
1634 3795
236 565
4041 4626
934 3865
2513 2835
239 565
1239 3066
136...

output:

1 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 21 22 24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 52 53 54 55 56 58 59 60 61 62 63 64 65 66 67 70 71 73 75 76 77 78 79 80 81 83 84 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 11...

result:

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

Test #6:

score: 10
Accepted
time: 72ms
memory: 10196kb

input:

193872 190790 1
1 55918
61723 111652
61723 106905
61723 146471
8591 47114
3781 26833
61723 175724
61723 105145
12561 22256
61723 167628
61723 152637
61723 89452
61723 126604
61723 87227
61723 80698
61723 72291
61723 96877
61723 122100
61723 83795
10417 42641
61723 158895
61723 107569
61723 164698
61...

output:

781 920 964 1035 1110 1131 1395 1426 1485 1691 1731 1818 1888 1983 2056 2124 2215 2224 2269 2333 2347 2400 2419 2440 2442 2446 2469 2477 2482 2626 2681 2683 2818 2822 2848 2858 2887 2931 2992 3004 3012 3040 3091 3120 3124 3134 3138 3172 3182 3188 3195 3267 3293 3366 3398 3492 3497 3514 3553 3622 363...

result:

ok 15827 numbers

Test #7:

score: 10
Accepted
time: 70ms
memory: 9968kb

input:

183551 186029 1
1 18923
46775 110591
46775 147364
46775 151335
46775 154945
46775 178847
46775 173705
46775 91772
46775 81093
46775 103570
46775 66868
46775 91670
46775 129650
46775 149481
46775 182893
46775 115551
46775 167292
46775 182574
46775 95438
46775 167281
46775 160712
46775 121691
46775 12...

output:

745 804 865 899 1129 1205 1261 1366 1431 1491 1572 1695 1700 1740 1835 1862 1871 1883 1926 1986 1994 2198 2214 2229 2285 2313 2359 2374 2413 2440 2459 2477 2486 2493 2506 2529 2532 2545 2546 2557 2588 2622 2642 2676 2771 2778 2812 2821 2822 2825 2939 2963 3039 3058 3061 3106 3138 3143 3167 3199 3209...

result:

ok 10193 numbers

Test #8:

score: 0
Wrong Answer
time: 90ms
memory: 10464kb

input:

180643 198737 94738
48353 166027
87663 136789
93307 135408
19654 33351
26552 33351
19265 33351
111942 134907
65187 149795
119612 170991
2417 33351
79279 166110
114686 162975
54701 163928
43129 116584
66103 139188
107280 147888
26067 33351
104751 139808
63876 148071
39714 129382
72905 148130
25384 33...

output:

1 2 4 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 38 40 41 43 44 45 46 47 48 49 50 52 53 54 55 56 57 60 61 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 83 84 85 86 87 88 89 91 92 93 94 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 1...

result:

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

Test #9:

score: 0
Wrong Answer
time: 79ms
memory: 10232kb

input:

191508 185305 100905
63990 91135
7954 91135
17174 91135
39427 91135
1129 91135
78418 91135
75781 91135
7987 91135
51528 91135
148938 181214
40890 91135
67657 91135
56216 91135
29882 91135
33981 91135
76412 91135
115229 151727
98300 104478
182577 190282
125477 163728
68488 91135
64154 91135
20562 911...

output:

1 2 3 4 6 7 8 9 10 11 12 13 15 17 18 19 20 22 23 24 25 26 27 28 29 30 31 32 34 35 36 37 39 41 43 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 63 64 65 66 67 68 69 70 72 74 75 77 78 79 80 81 83 84 85 86 87 88 89 90 91 92 93 94 96 97 98 99 101 102 103 104 105 107 108 109 110 112 113 114 115 116 ...

result:

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

Test #10:

score: 0
Wrong Answer
time: 79ms
memory: 10248kb

input:

191846 183854 90869
55728 85721
9713 85721
57235 85721
130204 144564
77210 85721
161065 162256
8962 85721
168055 177244
168055 174207
6371 85721
89768 136908
45508 85721
168055 185778
35520 85721
43450 85721
18758 85721
161027 162664
73184 85721
11364 85721
45366 85721
121115 163577
168055 190467
16...

output:

1 2 3 4 5 6 7 9 10 11 13 14 15 16 18 19 20 22 23 24 25 27 28 29 30 31 32 33 34 35 37 38 40 41 43 44 46 47 48 49 50 51 52 53 54 55 57 58 59 60 61 62 63 64 65 66 69 70 71 72 74 75 76 77 78 79 80 81 82 83 85 86 87 88 89 90 91 93 94 95 96 97 98 99 100 101 102 103 104 105 106 108 109 110 111 112 113 114 ...

result:

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