ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185081 | #2400. 椅子 | tkswls | 100 | 1097ms | 11040kb | C++11 | 2.2kb | 2023-09-21 11:14:37 | 2023-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;
}
Details
小提示:点击横条可展开更详细的信息
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