QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #447946 | #8528. Chords | ucup-team3215 | RE | 36ms | 341304kb | C++20 | 796b | 2024-06-19 04:12:22 | 2024-06-19 04:12:22 |
Judging History
answer
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
constexpr int N = 1e5 + 1;
int maxl[2 * N][700], l[2 * N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
vector<array<int, 2>> v(n);
fill(l, l + 2 * N, -1);
for (auto& [a, b]: v) cin >> a >> b, --a, --b;
for (auto& [a, b]: v) l[b] = a;
fill(maxl[0] + 1, maxl[1], -1);
maxl[0][0] = 2 * N;
for (int i = 1; i < 2 * n; ++i) {
copy(maxl[i - 1], maxl[i], maxl[i]);
if (!~l[i]) continue;
int j = 0; while (maxl[i - 1][j] > l[i]) ++j;
for (int k = 0; ~maxl[l[i]][k]; ++k) maxl[i][j + k] = max(maxl[i][j + k], min(l[i], maxl[l[i]][k]));
}
int ans = 0;
while (~maxl[2 * n - 1][ans]) ++ans;
cout << ans - 1 << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6268kb
input:
5 1 2 4 10 7 9 3 5 6 8
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4564kb
input:
1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 6188kb
input:
2 1 3 2 4
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 6332kb
input:
2 1 4 2 3
output:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
3 3 5 1 4 2 6
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4300kb
input:
4 2 7 1 6 3 8 4 5
output:
2
result:
ok 1 number(s): "2"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4640kb
input:
6 8 9 6 7 4 10 1 5 11 12 2 3
output:
5
result:
ok 1 number(s): "5"
Test #8:
score: 0
Accepted
time: 1ms
memory: 4444kb
input:
9 2 8 10 17 9 15 1 12 6 14 3 13 4 11 5 7 16 18
output:
4
result:
ok 1 number(s): "4"
Test #9:
score: 0
Accepted
time: 0ms
memory: 4628kb
input:
13 8 16 2 13 14 23 10 11 7 17 6 24 12 18 9 20 4 15 19 21 3 26 1 25 5 22
output:
6
result:
ok 1 number(s): "6"
Test #10:
score: 0
Accepted
time: 1ms
memory: 4496kb
input:
19 34 35 4 20 9 31 12 17 18 38 23 29 19 30 25 26 10 36 1 7 13 37 2 11 8 32 6 28 16 24 5 27 14 21 15 22 3 33
output:
8
result:
ok 1 number(s): "8"
Test #11:
score: 0
Accepted
time: 1ms
memory: 4480kb
input:
28 9 45 7 19 15 40 42 44 26 31 20 22 16 55 6 34 41 56 28 51 2 33 36 53 3 13 37 52 4 46 12 48 21 27 24 30 23 38 1 32 8 14 43 54 11 17 47 49 29 35 5 25 18 39 10 50
output:
10
result:
ok 1 number(s): "10"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5632kb
input:
42 2 66 29 75 5 45 8 53 50 72 25 44 15 47 6 57 64 68 26 80 32 49 65 70 27 54 37 58 18 36 10 48 3 63 28 60 30 76 16 41 7 83 21 24 14 17 31 67 62 71 20 74 11 33 43 84 40 61 19 69 35 82 13 42 34 79 12 73 9 51 4 23 77 81 22 59 1 52 39 55 38 56 46 78
output:
11
result:
ok 1 number(s): "11"
Test #13:
score: 0
Accepted
time: 1ms
memory: 4684kb
input:
63 40 105 6 104 45 83 16 22 31 34 51 57 64 92 75 112 70 82 65 121 32 93 18 60 30 68 72 77 86 101 10 47 85 94 36 71 11 35 27 126 56 74 15 52 19 91 88 110 76 97 25 33 58 109 42 54 12 26 73 107 99 118 29 106 44 90 3 9 23 122 14 79 87 116 4 81 17 111 41 53 50 123 38 124 13 114 67 96 5 100 55 115 43 62 4...
output:
17
result:
ok 1 number(s): "17"
Test #14:
score: 0
Accepted
time: 1ms
memory: 6716kb
input:
94 109 118 69 152 93 185 111 162 17 188 15 175 35 123 13 95 72 186 83 160 52 117 24 159 128 163 56 179 141 168 25 58 44 82 47 53 78 172 100 105 70 106 143 164 4 88 99 182 98 146 57 77 38 112 91 149 45 174 125 138 26 34 37 121 62 134 97 187 2 66 22 40 153 181 86 108 19 155 33 130 103 177 11 21 18 126...
output:
21
result:
ok 1 number(s): "21"
Test #15:
score: 0
Accepted
time: 1ms
memory: 6116kb
input:
141 31 127 1 73 84 94 158 254 129 208 35 114 112 201 182 222 18 259 27 267 67 271 14 160 22 269 89 161 57 58 49 86 8 184 202 256 24 43 194 198 225 273 204 265 79 270 66 249 54 250 130 268 26 162 165 261 197 257 119 279 216 232 21 274 151 179 106 140 28 48 122 206 65 186 3 177 90 92 15 105 163 262 14...
output:
32
result:
ok 1 number(s): "32"
Test #16:
score: 0
Accepted
time: 1ms
memory: 6056kb
input:
211 101 338 116 315 84 296 142 211 22 419 260 266 157 261 231 360 95 100 27 111 286 409 355 372 50 348 97 178 39 349 153 217 63 203 236 289 156 278 37 311 40 306 282 384 113 240 168 365 5 89 190 322 71 414 77 191 10 325 87 357 321 376 370 380 207 362 30 165 9 170 128 287 43 398 56 180 310 335 42 70 ...
output:
29
result:
ok 1 number(s): "29"
Test #17:
score: 0
Accepted
time: 1ms
memory: 6276kb
input:
316 433 483 190 220 85 439 171 209 459 479 4 63 335 434 315 400 55 155 125 558 457 619 90 187 135 301 172 497 124 354 101 363 140 312 288 425 99 513 147 516 120 122 143 180 138 500 78 617 123 191 231 615 268 536 227 417 32 67 360 554 263 553 108 165 105 257 295 620 95 212 21 319 87 464 356 559 266 6...
output:
45
result:
ok 1 number(s): "45"
Test #18:
score: 0
Accepted
time: 1ms
memory: 9256kb
input:
474 177 498 736 821 556 671 366 896 11 519 110 409 282 813 219 355 516 562 395 893 388 436 52 767 174 490 627 911 23 796 280 468 724 947 367 371 324 872 484 578 125 163 93 218 549 916 272 649 694 704 86 716 420 508 569 905 329 805 386 433 32 175 169 898 6 809 456 659 688 914 143 803 405 506 103 682 ...
output:
53
result:
ok 1 number(s): "53"
Test #19:
score: 0
Accepted
time: 1ms
memory: 9904kb
input:
711 394 512 506 1310 203 763 470 1161 548 1183 94 383 131 1123 467 478 141 695 969 1128 210 211 1045 1236 1184 1258 536 658 53 1174 115 687 648 911 410 735 266 732 226 1300 646 826 952 1019 353 1387 60 533 972 1221 418 1360 162 677 166 981 730 1130 859 1414 252 365 129 515 258 581 214 1290 1133 1289...
output:
61
result:
ok 1 number(s): "61"
Test #20:
score: 0
Accepted
time: 0ms
memory: 11416kb
input:
1066 1612 1799 593 928 560 965 683 1118 1058 1221 664 879 696 1724 54 102 1580 1588 599 1444 796 1749 35 1831 1 1261 299 1420 607 1048 147 643 873 1405 450 1080 1310 1489 1029 1658 183 752 666 1797 211 1485 51 802 42 673 1484 1811 540 561 934 1869 571 2081 1070 1248 362 1149 641 740 1540 1755 1329 1...
output:
82
result:
ok 1 number(s): "82"
Test #21:
score: 0
Accepted
time: 2ms
memory: 14384kb
input:
1599 668 1208 169 1885 106 2776 28 96 812 2453 2216 3175 783 2096 1005 1448 1430 1831 1252 3133 957 2070 2278 3096 747 1967 1765 2448 2377 2694 1522 1993 529 1006 329 771 130 1634 2057 2243 1222 3030 410 2565 1654 2264 1117 1387 1168 2360 2292 2848 1386 1460 2101 2124 671 3156 2215 2829 637 2782 20 ...
output:
95
result:
ok 1 number(s): "95"
Test #22:
score: 0
Accepted
time: 0ms
memory: 17636kb
input:
2398 3145 4490 88 211 1400 3788 3415 3441 889 3689 731 2304 2530 3700 2336 4449 3760 4420 2858 2932 1950 3588 1225 4526 1090 3288 521 2786 2196 4509 1057 2779 138 4514 882 3907 1393 3478 476 996 1410 4368 167 937 716 1773 458 4070 2527 4059 23 653 2720 4233 504 733 3367 3967 985 4483 300 918 1210 29...
output:
112
result:
ok 1 number(s): "112"
Test #23:
score: 0
Accepted
time: 0ms
memory: 26004kb
input:
3597 1586 6330 130 6292 3020 3385 874 5423 727 3192 329 2042 1352 2951 622 3427 4344 5462 2152 3104 521 5655 3682 5793 2324 2452 559 2822 4260 4634 4549 5092 245 2665 4872 5563 4717 5574 1909 2400 1456 4161 1546 3255 4454 5449 1027 4348 1083 4115 4715 6687 2093 6654 1851 4449 2731 4648 52 6819 2174 ...
output:
155
result:
ok 1 number(s): "155"
Test #24:
score: 0
Accepted
time: 0ms
memory: 35492kb
input:
5395 6550 9543 608 6746 1809 2339 3025 7758 1781 3543 6472 8170 6599 6801 5698 10446 1004 1449 6068 8618 1783 3263 2553 10510 4676 7024 5560 8498 5187 9289 1406 9596 7180 9101 6262 6534 964 8578 128 3469 1429 8001 3289 10484 5369 6694 680 4256 2086 4761 3936 4069 5487 8704 1580 9873 1600 10687 5555 ...
output:
189
result:
ok 1 number(s): "189"
Test #25:
score: 0
Accepted
time: 7ms
memory: 48924kb
input:
8092 1215 1887 813 12062 6710 9368 3227 3301 3923 9087 10036 11031 4632 13551 6161 13621 11190 12323 1993 14422 1012 15346 9369 11317 10356 11487 6181 14543 9245 10856 6898 10739 9132 11811 4357 5662 10216 11646 10857 14436 4238 7756 4359 5479 10547 13421 10704 11950 1089 2415 12928 13119 4629 5742 ...
output:
222
result:
ok 1 number(s): "222"
Test #26:
score: 0
Accepted
time: 12ms
memory: 72252kb
input:
12138 7599 9917 3613 15148 11028 19684 1426 22404 11772 12554 5840 19850 7493 23645 10133 18786 7322 11394 7703 22318 12434 21398 12972 13383 4041 7101 778 8840 5943 6841 7964 22934 4228 4919 14952 22462 9113 11699 20909 22889 3146 22742 9506 13307 42 5163 12325 15531 14618 15980 473 9087 4510 11886...
output:
275
result:
ok 1 number(s): "275"
Test #27:
score: 0
Accepted
time: 12ms
memory: 105272kb
input:
18207 5719 7227 5128 5741 8940 11851 16753 33871 1424 32292 21698 35542 5701 29850 18589 21605 25389 33498 14510 18018 5107 9109 9220 28209 16825 34820 8350 24784 5988 29007 19998 31825 5452 11627 143 19492 12282 24769 6869 19440 15281 35032 4094 32856 14159 30933 24157 33815 11007 27106 4584 9559 1...
output:
333
result:
ok 1 number(s): "333"
Test #28:
score: 0
Accepted
time: 11ms
memory: 154984kb
input:
27310 24313 53960 6447 29206 43114 50834 27178 44779 3360 18859 14242 45748 12095 37757 19973 50026 10917 31240 2673 19537 614 49708 20607 34501 30489 47517 32483 50528 40601 54120 21955 27248 13200 24329 2270 44545 18220 43233 4971 40485 32983 50853 11602 28285 16456 27029 38593 39939 11203 27590 3...
output:
415
result:
ok 1 number(s): "415"
Test #29:
score: 0
Accepted
time: 31ms
memory: 228360kb
input:
40965 29289 34280 24803 56563 67444 80519 31854 33649 40599 45946 32665 43594 25116 74459 34269 67811 19273 74683 25457 48566 17902 38761 59097 66404 46123 46353 4097 72253 16449 35843 7325 31322 4583 38732 12212 27161 27741 47551 28607 64517 7589 30534 27668 36844 23967 41378 37746 79383 24321 4524...
output:
504
result:
ok 1 number(s): "504"
Test #30:
score: 0
Accepted
time: 36ms
memory: 341304kb
input:
61447 95816 105164 417 61176 65717 122347 48383 55460 59094 95622 9841 114890 35269 71562 6577 77322 18726 90356 67239 77364 11869 43467 97014 102496 93723 108939 32523 121580 18264 58143 7802 57789 68519 119838 76777 107223 11817 114522 61852 73702 37555 114206 6185 29287 39517 68647 92822 99787 30...
output:
632
result:
ok 1 number(s): "632"
Test #31:
score: -100
Runtime Error
input:
92170 27537 41477 49719 84219 16517 119320 15831 182334 31380 58321 6736 174438 71292 156683 67132 92947 29385 56237 107332 116382 50809 72175 13117 85487 118338 131599 15064 16769 62021 156609 15328 46733 2505 46032 112285 137473 23148 134463 65168 154531 104937 157907 102537 181386 42465 168217 13...