QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108318 | #6308. Magic | zqyyy | TL | 2911ms | 7212kb | C++17 | 746b | 2023-05-24 15:01:33 | 2023-05-24 15:01:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=5007;
int n, mat[N]; bool vis[N];
struct seg {int l, r;} a[N];
bitset<N> bs[N];
bool dfs(int x) {
for (int i=bs[x]._Find_first(); i<=n; i=bs[x]._Find_next(i))
if (!vis[i]) {
vis[i]=true;
if (!mat[i] || dfs(mat[i])) return mat[i]=x, true;
}
return false;
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d%d", &a[i].l, &a[i].r);
sort(a+1, a+n+1, [&](auto x, auto y) {return x.l<y.l;});
for (int i=1; i<=n; i++)
for (int j=i+1; j<=n; j++) {
if (a[i].r<a[j].l) break;
if (a[i].r<a[j].r) bs[i].set(j);
}
int ans=2*n;
for (int i=1; i<=n; i++)
fill(vis+1, vis+n+1, false), ans-=dfs(i);
printf("%d\n", ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3620kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 6648kb
input:
5000 7985 7987 42 46 1591 1593 407 410 6305 6306 1456 1457 5874 5875 7135 7137 7041 7046 6813 6815 8868 8871 665 666 4055 4056 9789 9796 7067 7068 4745 4746 5167 5171 1735 1737 2125 2128 1444 1447 1348 1352 6087 6090 1381 1384 1600 1601 5187 5190 2801 2802 8449 8450 9376 9377 4021 4024 2674 2676 490...
output:
8134
result:
ok 1 number(s): "8134"
Test #3:
score: 0
Accepted
time: 0ms
memory: 6744kb
input:
5000 3171 3172 4062 4064 4647 4651 3670 3673 7112 7114 9714 9717 3781 3789 8422 8426 457 460 5450 5454 7113 7122 6313 6320 9969 9973 828 832 6878 6892 4476 4483 892 903 251 259 6304 6315 130 134 9206 9215 2679 2686 9090 9091 8222 8228 9374 9375 2985 2989 3397 3401 4916 4918 6819 6821 883 889 2516 25...
output:
7047
result:
ok 1 number(s): "7047"
Test #4:
score: 0
Accepted
time: 3ms
memory: 6692kb
input:
5000 7269 7286 1979 1990 4225 4241 7866 7872 2052 2067 1508 1514 2366 2370 3488 3493 8979 8987 302 306 6730 6732 7704 7705 5528 5544 7420 7425 4705 4712 593 601 6662 6668 5228 5257 2008 2013 548 562 7949 7950 1017 1020 1025 1028 6 11 4722 4736 9945 9950 8368 8379 6781 6787 4558 4566 400 404 858 864 ...
output:
6191
result:
ok 1 number(s): "6191"
Test #5:
score: 0
Accepted
time: 10ms
memory: 6752kb
input:
5000 3005 3008 7811 7821 2832 2840 9812 9818 3947 3952 3629 3665 7443 7455 1473 1478 1467 1494 5499 5508 229 232 9477 9498 9500 9514 4769 4775 9488 9503 1514 1520 5101 5112 2455 2456 3558 3610 9072 9188 659 666 2286 2301 9735 9782 5959 5984 5823 5844 1827 1835 3658 3681 3494 3503 1016 1018 3418 3420...
output:
5636
result:
ok 1 number(s): "5636"
Test #6:
score: 0
Accepted
time: 396ms
memory: 6716kb
input:
5000 1017 1019 5731 5744 8592 8697 3414 3561 277 356 4421 4458 7969 7989 3733 3759 1975 1986 6895 6898 8580 8657 2320 2325 6494 6510 3574 3616 7721 7780 7756 7835 1744 1748 5085 5102 5428 5588 6823 6847 9348 9405 1969 2064 1152 1242 3676 3679 5569 5713 213 248 8277 8285 3739 3782 5582 5604 9076 9105...
output:
5225
result:
ok 1 number(s): "5225"
Test #7:
score: 0
Accepted
time: 97ms
memory: 6844kb
input:
5000 4269 4768 7697 7804 4289 4316 6641 6742 3782 3871 9785 9858 1845 1979 6300 6412 8194 8616 3 18 8536 8790 7 129 4406 4448 3556 3609 2800 2918 3081 3164 1854 1948 8220 8546 7070 7318 1117 1195 8770 8944 5754 5760 8512 8590 5714 5829 6132 6156 8252 8381 889 1149 1899 1949 4675 4683 4282 4426 2977 ...
output:
5124
result:
ok 1 number(s): "5124"
Test #8:
score: 0
Accepted
time: 446ms
memory: 6944kb
input:
5000 1247 1337 3192 3474 7887 8008 2912 3065 4356 4573 9268 9376 987 1165 6972 7155 580 668 331 718 455 640 4815 4854 3783 3988 8426 8579 7459 7563 1991 2482 9585 9973 7562 7627 7472 8428 86 320 8319 8331 8596 8953 5729 6468 7209 7364 1026 1246 6575 6608 5048 5050 1957 2531 9408 9489 3092 3096 845 1...
output:
5079
result:
ok 1 number(s): "5079"
Test #9:
score: 0
Accepted
time: 935ms
memory: 6964kb
input:
5000 1356 3126 3141 3369 3524 4274 1330 1812 4781 5129 2713 2743 139 741 1978 2219 1841 3301 6951 7599 7003 8073 6492 6563 9044 9185 7533 7745 9596 9862 2807 3582 4284 4486 3483 4771 7683 8441 1677 2359 4700 4752 861 2053 701 1098 1283 2450 1997 2270 6794 7284 9469 9496 280 731 1125 1683 2283 2539 3...
output:
5059
result:
ok 1 number(s): "5059"
Test #10:
score: 0
Accepted
time: 1569ms
memory: 7020kb
input:
5000 3676 4155 4813 4957 6926 7118 6695 6826 3624 3847 1696 2051 5628 7796 1145 2640 244 803 3089 3246 101 2013 7644 8249 6252 9848 3352 5216 1683 2490 114 1135 2868 3037 3516 4495 4122 5522 2488 3785 138 579 4716 5036 2918 4052 491 712 2751 4533 56 495 2085 3038 6523 6768 5592 6555 6040 6965 9716 9...
output:
5061
result:
ok 1 number(s): "5061"
Test #11:
score: 0
Accepted
time: 2165ms
memory: 7192kb
input:
5000 7645 8814 2855 4135 5584 7079 3371 3514 4858 6115 1160 2738 1016 1244 1090 2532 5407 5453 1272 2001 2660 3153 6849 7796 8127 9419 2827 4055 4303 6893 4269 7945 4804 5316 6680 8387 3561 3848 984 4841 1385 1638 8101 8830 453 9062 6072 9218 3304 3615 8899 9596 4525 4750 481 4112 2187 4061 8254 876...
output:
5077
result:
ok 1 number(s): "5077"
Test #12:
score: 0
Accepted
time: 2670ms
memory: 7012kb
input:
5000 4947 5073 6010 6191 503 3970 4578 5766 5622 9195 7180 7616 2542 6653 1807 7852 6760 7614 612 8136 1166 3586 3157 6433 1032 2855 988 6736 4858 8152 319 2208 6507 9016 7803 9346 773 8940 3646 5774 2504 9762 5186 5449 2100 4949 8352 9818 2719 9527 2963 9138 4577 4992 7977 9142 1697 5118 5661 8807 ...
output:
5087
result:
ok 1 number(s): "5087"
Test #13:
score: 0
Accepted
time: 2613ms
memory: 7108kb
input:
5000 3569 5853 3805 9296 6077 8227 5992 8647 3355 6981 2910 5083 1995 2252 5990 6301 3466 4029 2481 4730 5314 6440 2567 5631 4299 5829 568 9502 6066 9604 2527 4983 4791 8244 5023 7341 2629 3977 2192 2462 2137 3400 1380 7387 2864 7832 2975 7576 2840 2928 5924 6542 1007 1728 933 4876 1169 7206 4836 49...
output:
5104
result:
ok 1 number(s): "5104"
Test #14:
score: 0
Accepted
time: 14ms
memory: 6764kb
input:
5000 871 9565 987 9507 2149 8926 2382 6310 2073 8964 3670 5666 2227 8887 2563 8719 4107 7947 3087 8457 2852 6075 1423 9289 1042 6980 969 9516 98 7452 4069 7966 2038 6482 4364 5319 3057 8472 2412 6295 523 9739 2026 6488 4777 7612 1761 9120 2740 6131 1295 9353 2241 8880 1034 6984 428 7287 376 7313 160...
output:
7501
result:
ok 1 number(s): "7501"
Test #15:
score: 0
Accepted
time: 7ms
memory: 6708kb
input:
4999 3207 8395 3675 8161 4846 5076 2968 6015 1037 9480 4634 5182 548 7225 2984 6007 2316 6341 1164 6917 460 7269 3885 8056 4254 5372 2730 6134 4906 5046 3282 5858 1300 6849 3875 8061 1414 6792 786 7106 1201 9398 4052 5473 1236 6881 3066 5966 182 7408 2875 8561 2229 8884 2135 8931 2397 8800 427 9785 ...
output:
7499
result:
ok 1 number(s): "7499"
Test #16:
score: 0
Accepted
time: 0ms
memory: 6632kb
input:
4999 5431 5436 2916 2917 582 587 137 144 6660 6661 4890 4897 5300 5303 66 72 5708 5711 3735 3737 5298 5301 1900 1912 1304 1306 9900 9902 537 541 5019 5020 5334 5338 7279 7283 8186 8190 3660 3665 458 460 4588 4589 9828 9832 7850 7852 7561 7564 8193 8195 1872 1875 3638 3641 6346 6347 2378 2379 4187 41...
output:
8131
result:
ok 1 number(s): "8131"
Test #17:
score: 0
Accepted
time: 0ms
memory: 6700kb
input:
4999 8363 8375 1371 1372 1038 1045 1741 1742 9672 9673 5734 5738 8369 8372 1414 1427 7767 7771 7970 7983 4403 4409 3720 3724 8958 8959 7311 7312 6365 6378 331 338 3975 3982 4356 4357 6195 6206 3009 3010 7591 7602 6554 6558 1195 1202 4417 4418 7990 7993 4900 4914 7921 7927 2504 2508 5043 5047 4324 43...
output:
7066
result:
ok 1 number(s): "7066"
Test #18:
score: 0
Accepted
time: 2ms
memory: 6768kb
input:
4999 5839 5845 6903 6906 3785 3798 5232 5253 1216 1227 378 402 7691 7693 1359 1369 5901 5908 5117 5118 7752 7755 7229 7254 650 674 4571 4584 7617 7660 2197 2208 503 509 4965 4969 2375 2385 2743 2745 757 768 1988 1994 667 673 5053 5062 9796 9818 6843 6867 577 581 4514 4538 2248 2261 3025 3035 672 699...
output:
6366
result:
ok 1 number(s): "6366"
Test #19:
score: 0
Accepted
time: 11ms
memory: 6740kb
input:
4999 1052 1056 1180 1191 606 614 3449 3480 811 827 9191 9233 9559 9578 6572 6587 2932 2933 2245 2293 4081 4088 5994 6034 6534 6565 7417 7418 2123 2160 226 232 9627 9652 9836 9857 1734 1748 1062 1063 3811 3822 5006 5030 9942 9966 692 721 3694 3699 543 567 1379 1396 9691 9736 7961 7962 3752 3755 4124 ...
output:
5622
result:
ok 1 number(s): "5622"
Test #20:
score: 0
Accepted
time: 83ms
memory: 6960kb
input:
4999 441 443 8409 8433 3652 3682 5308 5375 2255 2299 7239 7248 6585 6659 7834 7921 8492 8532 4806 4881 6294 6387 1324 1383 2737 2809 1045 1129 6352 6399 8756 8775 5120 5171 7981 8016 8598 8608 839 883 8506 8518 694 833 4038 4043 2357 2366 2439 2581 5560 5688 7014 7040 9281 9317 2769 2825 7279 7280 7...
output:
5259
result:
ok 1 number(s): "5259"
Test #21:
score: 0
Accepted
time: 228ms
memory: 6852kb
input:
4999 9430 9436 601 695 480 515 9413 9433 3585 3785 9228 9318 3219 3483 5648 5842 8273 8342 3379 3398 1716 1797 6100 6152 1185 1322 4411 4633 4321 4364 2521 2561 4953 5009 5221 5311 378 513 4058 4140 5184 5314 631 632 4509 4536 6977 7020 3309 3443 7676 7740 507 934 8420 8502 238 436 8159 8423 570 654...
output:
5134
result:
ok 1 number(s): "5134"
Test #22:
score: 0
Accepted
time: 351ms
memory: 7112kb
input:
4999 4317 4457 8422 8554 4906 5161 6527 7079 1220 1350 1010 1032 3592 3676 3700 3719 5038 5079 4532 4535 4677 4788 3371 3527 857 987 6826 7186 5958 6044 7846 8542 4805 5561 4191 4390 2669 2682 1594 1937 504 605 6856 7251 1240 1528 5170 5201 481 587 2031 2248 9508 9951 6542 6867 8685 8889 7007 7044 2...
output:
5066
result:
ok 1 number(s): "5066"
Test #23:
score: 0
Accepted
time: 940ms
memory: 7020kb
input:
4999 6643 6946 2015 2127 7853 8773 1592 2602 6495 6880 8086 8933 8599 9434 3350 3932 5285 5348 400 658 5843 5936 5506 5522 5762 6131 1290 1653 6150 6551 479 660 2991 2996 7500 7632 3316 3491 8851 8956 8481 8792 5143 5191 1342 1508 6074 6108 2644 3505 7497 7757 7955 8228 2214 2571 1938 3123 992 1383 ...
output:
5059
result:
ok 1 number(s): "5059"
Test #24:
score: 0
Accepted
time: 1425ms
memory: 7212kb
input:
4999 7318 7668 3670 3794 243 2954 56 1573 5805 7851 9 2407 454 1393 725 1779 9709 9871 3481 3522 9129 9475 7811 9385 1017 1681 3065 3462 4135 4655 34 755 974 1071 865 1072 4288 4471 7738 8449 15 242 8161 9263 1613 2188 5321 5847 3330 3924 7839 8239 8158 8516 4142 4315 5039 5077 6081 6592 5677 5862 6...
output:
5056
result:
ok 1 number(s): "5056"
Test #25:
score: 0
Accepted
time: 2018ms
memory: 6996kb
input:
4999 4992 5718 358 2562 4128 4297 246 3376 907 2019 2076 3951 2850 6203 617 4942 192 2300 188 2135 293 3550 3026 4557 2493 6702 3476 7470 3937 6193 3725 3762 813 4969 4810 5944 5398 7553 4357 7793 1809 2988 6862 7467 3835 4012 3271 5647 6768 9968 6028 6634 5914 7535 8012 8594 7361 7524 397 1573 3374...
output:
5070
result:
ok 1 number(s): "5070"
Test #26:
score: 0
Accepted
time: 2503ms
memory: 7012kb
input:
4999 3163 8330 9027 9342 106 4633 7484 8163 6892 9248 1330 2769 4258 8600 800 3843 3355 7035 1899 6283 1440 3789 1364 3473 4916 9317 3603 8620 2184 3368 6190 7077 411 1780 3437 4966 6980 7333 1125 6406 5861 7744 712 9508 1867 3548 1963 8426 7811 9570 5396 6271 7195 9829 5219 6486 2337 4288 3364 5668...
output:
5086
result:
ok 1 number(s): "5086"
Test #27:
score: 0
Accepted
time: 2671ms
memory: 7096kb
input:
4999 845 1599 782 3268 1007 1460 6298 8042 6934 9545 2486 5021 5151 6493 1631 2090 1345 2253 1539 2735 8856 9538 1822 2957 3777 8337 881 3952 7171 7325 5346 7124 4341 8176 2830 8935 4010 5545 2746 8196 5410 6949 4496 5499 8194 9133 3221 7828 2213 4329 125 6246 8259 9008 1319 5858 4767 9114 3675 5041...
output:
5096
result:
ok 1 number(s): "5096"
Test #28:
score: 0
Accepted
time: 411ms
memory: 6968kb
input:
5000 5185 5200 9772 9776 818 854 2803 2815 9028 9075 8856 8893 6548 6550 4312 4423 5811 5822 3900 3933 1402 1546 2429 2456 7808 7823 6090 6155 3087 3089 9015 9110 1633 1755 9497 9649 2280 2417 151 205 7052 7106 6438 6447 6835 6867 6852 6898 2540 2556 57 88 7609 7622 6781 6798 7771 7840 5333 5343 758...
output:
5225
result:
ok 1 number(s): "5225"
Test #29:
score: 0
Accepted
time: 51ms
memory: 6796kb
input:
4999 5156 5247 3007 3065 4110 4138 1814 1873 132 163 4521 4554 3466 3494 9630 9671 3914 3942 969 992 3365 3423 7136 7149 6873 6930 6632 6683 5655 5683 2770 2796 4909 4970 5830 5852 8341 8476 9036 9050 993 1278 8339 8366 22 148 3554 3649 2484 2487 1218 1226 9914 9930 9427 9431 6305 6320 1841 1890 912...
output:
5224
result:
ok 1 number(s): "5224"
Test #30:
score: 0
Accepted
time: 2911ms
memory: 7148kb
input:
5000 1708 9430 234 2683 2108 4320 841 2215 2421 7664 8977 9327 4221 8868 723 7208 248 1554 4913 8512 3388 4471 6180 7609 1325 5327 3476 8584 2105 9064 4369 5765 5088 5451 7147 9405 4204 7540 6394 7230 7138 9107 1623 8360 5166 6089 972 5847 1915 5345 6953 8309 552 1356 4718 9296 8414 9050 4645 8510 5...
output:
5097
result:
ok 1 number(s): "5097"
Test #31:
score: -100
Time Limit Exceeded
input:
5000 3714 3967 3165 6901 1796 7494 775 7440 6010 8297 4737 6454 2970 6630 1429 5812 3580 5112 3178 5868 628 7138 1525 8276 1583 4018 1341 4213 76 4851 6670 9978 7229 8292 377 2595 9362 9676 4205 6575 3942 7342 2940 3148 4892 5863 4389 8236 5176 5533 43 4387 2992 7261 5481 5751 5130 6273 6265 8123 62...