UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#185081#2400. 椅子tkswls1001097ms11040kbC++112.2kb2023-09-21 11:14:372023-09-21 12:24:11

answer

#include<bits/stdc++.h>
using namespace std;
int n, m, cnt;
struct node {
	int l, r;
} a[200005];
bool cmp(node p, node q) {
	return p.l < q.l;
}
struct XDT {
	int l, r, maxa, tag;
} b[800005];
inline void push_down(int p) {
	if (b[p].l == b[p].r) return;
	if (b[p].tag == 0) return;
	b[2 * p].maxa += b[p].tag;
	b[2 * p + 1].maxa += b[p].tag;
	b[2 * p].tag += b[p].tag;
	b[2 * p + 1].tag += b[p].tag;
	b[p].tag = 0;
}
inline void update(int p) {
	b[p].maxa = max(b[2 * p].maxa, b[2 * p + 1].maxa);
}
void build(int p, int l, int r) {
	b[p].l = l;
	b[p].r = r;
	b[p].tag = 0;
	if (l == r) {
		b[p].maxa = -(m - l + 1);
		return;
	}
	build(2 * p, l, (l + r) >> 1);
	build(2 * p + 1, ((l + r) >> 1) + 1, r);
	update(p);
}
void add(int p, int l, int r, int w) {
	if (r < l) return;
	if (b[p].l >= l && b[p].r <= r) {
		b[p].maxa += w;
		b[p].tag += w;
		return;
	}
	push_down(p);
	int mid = (b[p].l + b[p].r) >> 1;
	if (r <= mid) add(2 * p, l, r, w);
	else if (l > mid) add(2 * p + 1, l, r, w);
	else {
		add(2 * p, l, mid, w);
		add(2 * p + 1, mid + 1, r, w);
	}
	update(p);
}
inline int query(int p, int l, int r) {
	if (b[p].l >= l && b[p].r <= r) {
		return b[p].maxa;
	}
	push_down(p);
	int mid = (b[p].l + b[p].r) >> 1;
	if (r <= mid) return query(2 * p, l, r );
	else if (l > mid) return query(2 * p + 1, l, r );
	else {
		return max(query(2 * p, l, mid), query(2 * p + 1, mid + 1, r));
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int p, q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].l >> a[i].r;
		if (a[i].l - a[i].r >= -1) {
			a[i].l =  0;
			a[i].r = -1;
			cnt++;
		}
	}
	sort(a + 1, a + n + 1, cmp);
	build(1, 1, 1 + m);
	int ans = 0;
	int r = 1;
	while (a[r].l == 0 && r <= n) {
		if (a[r].l > a[r].r) {
			r++;
			continue;
		}
		add(1, 1, a[r].r, 1);
		r++;
	}
	add(1, 1, 1, cnt);
	ans = max(ans, query(1, 1, 1 + m));
	for (int i = 1; i <= m; i++) {
		while (a[r].l <= i && r <= n) {
			add(1, 1, a[r].r, 1);
			r++;
		}
		if (i == m) {
			ans = max(ans, -m + n);
			break;
		}
		add(1, i + 1, i + 1, cnt);
		ans = max(ans, query(1, i + 1, m + 1) - i);
	}
	cout << ans;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1280kb

input:

8 8
1 8
1 5
2 8
0 5
0 3
2 6
2 6
2 6

output:

1

result:

ok single line: '1'

Test #2:

score: 5
Accepted
time: 0ms
memory: 1268kb

input:

10 10
0 5
2 9
3 10
2 7
1 6
0 10
0 9
2 10
0 9
1 10

output:

2

result:

ok single line: '2'

Test #3:

score: 5
Accepted
time: 0ms
memory: 1280kb

input:

20 20
4 16
2 11
3 19
6 12
7 18
1 14
4 10
5 20
6 14
8 17
1 12
2 11
7 18
7 15
0 15
1 12
2 19
7 13
4 10...

output:

1

result:

ok single line: '1'

Test #4:

score: 5
Accepted
time: 0ms
memory: 1284kb

input:

96 93
2 67
5 61
4 74
15 68
3 63
40 91
14 58
6 66
9 57
18 85
13 63
40 85
17 89
16 73
10 72
15 74
15 6...

output:

7

result:

ok single line: '7'

Test #5:

score: 5
Accepted
time: 1ms
memory: 1284kb

input:

100 100
29 70
17 68
25 77
13 74
9 79
42 90
34 99
18 100
3 80
21 71
26 63
6 54
43 89
41 78
19 78
13 9...

output:

2

result:

ok single line: '2'

Test #6:

score: 5
Accepted
time: 1ms
memory: 1320kb

input:

952 954
182 871
114 769
110 694
91 741
22 509
53 841
124 858
16 465
160 789
24 720
96 939
56 689
313...

output:

64

result:

ok single line: '64'

Test #7:

score: 5
Accepted
time: 0ms
memory: 1332kb

input:

1000 1000
74 795
175 641
39 618
19 971
162 873
93 731
480 989
357 932
4 693
266 965
89 581
47 560
27...

output:

74

result:

ok single line: '74'

Test #8:

score: 5
Accepted
time: 0ms
memory: 1580kb

input:

4516 4690
665 4024
1062 3765
1573 4200
1035 4155
441 2678
31 3472
87 3450
146 2286
310 4267
1231 450...

output:

69

result:

ok single line: '69'

Test #9:

score: 5
Accepted
time: 4ms
memory: 1580kb

input:

5000 5000
62 4476
1146 3647
531 4569
1042 3464
2044 4817
2186 4584
2223 4892
1224 4761
1154 4943
147...

output:

250

result:

ok single line: '250'

Test #10:

score: 5
Accepted
time: 6ms
memory: 1608kb

input:

10000 5000
1106 4454
1138 4746
926 4805
609 4507
259 4543
1435 4211
790 3399
528 3426
38 4665
87 404...

output:

5347

result:

ok single line: '5347'

Test #11:

score: 5
Accepted
time: 7ms
memory: 1880kb

input:

10000 10000
2224 8599
3697 9779
1264 7760
266 8474
601 9386
5276 9907
4231 9619
2206 8589
3306 9731
...

output:

574

result:

ok single line: '574'

Test #12:

score: 5
Accepted
time: 59ms
memory: 6108kb

input:

93875 99655
0 25859
0 30798
0 89053
0 29230
0 93483
0 83280
0 47502
0 39669
0 69861
0 64184
0 35067
...

output:

14154

result:

ok single line: '14154'

Test #13:

score: 5
Accepted
time: 67ms
memory: 6152kb

input:

100000 100000
0 50602
0 56129
0 65965
0 75241
0 71832
0 26413
0 79671
0 73842
0 78772
0 94149
0 3483...

output:

25000

result:

ok single line: '25000'

Test #14:

score: 5
Accepted
time: 70ms
memory: 6100kb

input:

91057 96847
21419 89318
2406 89095
2941 51033
14888 77083
28023 74840
18260 62296
6297 51346
7735 88...

output:

134

result:

ok single line: '134'

Test #15:

score: 5
Accepted
time: 76ms
memory: 6164kb

input:

100000 100000
16723 78322
7205 66894
9839 72285
7661 85725
38680 93140
6182 88375
30785 99006
38538 ...

output:

5118

result:

ok single line: '5118'

Test #16:

score: 5
Accepted
time: 165ms
memory: 11028kb

input:

198495 197435
63738 165927
17757 117506
9207 170263
50748 141346
18132 120887
49285 188664
25304 190...

output:

11098

result:

ok single line: '11098'

Test #17:

score: 5
Accepted
time: 161ms
memory: 11036kb

input:

199260 192470
22818 156104
9228 171776
43025 139453
39938 135662
18272 171006
68109 171295
28220 116...

output:

15568

result:

ok single line: '15568'

Test #18:

score: 5
Accepted
time: 160ms
memory: 11036kb

input:

200000 200000
75002 167675
8656 181873
54606 156991
48075 167451
74414 194621
55633 180796
4565 1657...

output:

10484

result:

ok single line: '10484'

Test #19:

score: 5
Accepted
time: 159ms
memory: 11036kb

input:

200000 200000
59298 170956
2760 194028
35447 153792
1945 163425
73195 176225
62065 185526
85886 1916...

output:

10543

result:

ok single line: '10543'

Test #20:

score: 5
Accepted
time: 161ms
memory: 11040kb

input:

200000 200000
67496 171474
36806 170296
86759 193181
7951 171117
85324 184470
8949 171983
10465 1547...

output:

10575

result:

ok single line: '10575'

Extra Test:

score: 0
Extra Test Passed