QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43027 | #4270. Double Attendance | ppavic# | 0 | 6ms | 6024kb | C++ | 1.8kb | 2022-08-05 18:01:20 | 2024-05-26 01:03:50 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair < int , int > pii;
const int N = 3e5 + 500;
const int M = 2e6 + 500;
int n, m, k;
int dp[M][2];
vector < pii > S[2];
vector < int > v;
int gdje(int x, int tko){
if(S[tko].back().Y <= x || S[tko][0].X > x) return -1;
int gdje = upper_bound(S[tko].begin(), S[tko].end(), (pii){x, (int)1e9 + 100}) - S[tko].begin() - 1;
return S[tko][gdje].Y > x ? gdje : -1;
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for(int i = 0;i < n;i++){
int x, y; scanf("%d%d", &x, &y);
S[0].PB({x, y});
v.PB(x); v.PB(y - k - 1);
v.PB(x + k); v.PB(y - 1);
v.PB(x - k);
v.PB(x - 2 * k);
}
for(int i = 0;i < m;i++){
int x, y; scanf("%d%d", &x, &y);
S[1].PB({x, y});
v.PB(x - k);
v.PB(x); v.PB(y - k - 1);
v.PB(x + k); v.PB(y - 1);
v.PB(x - 2 * k);
}
sort(S[0].begin(), S[0].end());
sort(S[1].begin(), S[1].end());
v.PB(0);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
reverse(v.begin(), v.end());
while(v.back() < 0) v.pop_back();
reverse(v.begin(), v.end());
dp[0][0] = gdje(0, 0) != -1;
dp[0][1] = -(int)1e9;
int ans = dp[0][0];
for(int i = 1;i < (int)v.size();i++){
for(int tko = 0;tko < 2;tko++){
int tren = gdje(v[i], tko);
if(tren != -1 && tren != gdje(v[i - 1], tko))
dp[i][tko] = dp[i - 1][tko] + 1;
else
dp[i][tko] = dp[i - 1][tko];
int j = upper_bound(v.begin(), v.end(), v[i] - k) - v.begin();
if(j > 0)
dp[i][tko] = max(dp[i][tko], (tren != -1) + dp[j - 1][!tko]);
//printf("dp[ %d ][ %d ] = %d\n", v[i], tko, dp[i][tko]);
ans = max(ans, dp[i][tko]);
}
}
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 0ms
memory: 3892kb
input:
3 1 8 10 20 100 101 20 21 15 25
output:
3
result:
ok single line: '3'
Test #2:
score: -5
Wrong Answer
time: 0ms
memory: 3804kb
input:
1 5 3 1 100 1 2 2 3 3 4 4 5 5 6
output:
5
result:
wrong answer 1st lines differ - expected: '4', found: '5'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #104:
score: 6
Accepted
time: 0ms
memory: 3876kb
input:
1 1 1 0 1 0 1
output:
1
result:
ok single line: '1'
Test #105:
score: 0
Accepted
time: 1ms
memory: 4080kb
input:
1 2000 2 999999996 1000000000 336 337 502 503 1906 1907 963 964 1351 1352 1795 1796 1510 1511 304 305 1930 1931 1735 1736 1469 1470 338 339 813 814 182 183 209 210 321 322 849 850 721 722 394 395 889 890 1758 1759 1440 1441 560 561 1470 1471 1916 1917 793 794 1366 1367 158 159 1602 1603 214 215 1119...
output:
2000
result:
ok single line: '2000'
Test #106:
score: 0
Accepted
time: 4ms
memory: 3948kb
input:
2000 2000 249875 608195750 608695500 88455750 88955500 579210250 579710000 817091250 817591000 527736000 528235750 52473750 52973500 89955000 90454750 184407750 184907500 668165750 668665500 24487750 24987500 466266750 466766500 471764000 472263750 212393750 212893500 250874500 251374250 939530000 9...
output:
4000
result:
ok single line: '4000'
Test #107:
score: 0
Accepted
time: 4ms
memory: 3948kb
input:
2000 2000 249875 965017250 965517000 73963000 74462750 242878500 243378250 148925500 149425250 747126250 747626000 384307750 384807500 655172250 655672000 278360750 278860500 899050250 899550000 496251750 496751500 92953500 93453250 677661000 678160750 828085750 828585500 297351250 297851000 5887055...
output:
4000
result:
ok single line: '4000'
Test #108:
score: 0
Accepted
time: 2ms
memory: 4072kb
input:
2000 2000 499500 428 429 764235000 765234000 511488000 512487000 291 292 585414000 586413000 127 128 819 820 727 728 233766000 234765000 643 644 234 235 326 327 432 433 218781000 219780000 10989000 11988000 805194000 806193000 283716000 284715000 965034000 966033000 632367000 633366000 824 825 454 4...
output:
4000
result:
ok single line: '4000'
Test #109:
score: 0
Accepted
time: 4ms
memory: 4144kb
input:
2000 2000 499500 175 176 766233000 767232000 230 231 925 926 844 845 681318000 682317000 48951000 49950000 757 758 266 267 438561000 439560000 262737000 263736000 813 814 915084000 916083000 485514000 486513000 214785000 215784000 532467000 533466000 25 26 41958000 42957000 534 535 331 332 53 54 732...
output:
3999
result:
ok single line: '3999'
Test #110:
score: 0
Accepted
time: 4ms
memory: 4072kb
input:
2000 2000 1 97918740 97918742 612788646 612788648 709014683 709014684 550596486 550596488 611820813 611820815 742133170 742133172 999593290 999593292 65695562 65695563 984598976 984598977 285428771 285428773 334881813 334881814 751309389 751309390 635034524 635034526 202056719 202056720 472216430 47...
output:
4000
result:
ok single line: '4000'
Test #111:
score: 0
Accepted
time: 4ms
memory: 4100kb
input:
2000 2000 1000000000 762582513 763402869 685982674 685994777 607586653 607621748 725505868 725606928 287661547 287711487 961278566 961422544 282891861 282922769 388240582 388471546 305173664 305545845 17696180 17939334 267223086 267237726 251362344 251735629 957622587 957813570 321979347 321992100 7...
output:
2000
result:
ok single line: '2000'
Test #112:
score: 0
Accepted
time: 3ms
memory: 4040kb
input:
2000 2000 1000000000 675 676 1250 1251 1565 1566 211 212 951 952 250 251 1975 1976 775 776 795 796 85 86 212 213 293 294 1970 1971 627 628 1945 1946 688 689 1050 1051 223 224 288 289 476 477 137 138 613 614 1400 1401 1087 1088 801 802 734 735 1112 1113 51 52 1127 1128 546 547 881 882 276 277 680 681...
output:
2000
result:
ok single line: '2000'
Test #113:
score: 0
Accepted
time: 3ms
memory: 3920kb
input:
2000 2000 2000 683 684 170 171 1005 1006 1612 1613 330 331 280 281 1340 1341 1083 1084 355 356 1603 1604 1001 1002 873 874 1520 1521 1657 1658 1827 1828 1868 1869 655 656 1981 1982 184 185 900 901 1917 1918 1096 1097 956 957 987 988 536 537 921 922 317 318 869 870 1095 1096 1684 1685 762 763 1896 18...
output:
2000
result:
ok single line: '2000'
Test #114:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
89 1537 3 1761 1764 1885 1887 1489 1490 1523 1528 1491 1494 1204 1206 288 293 1433 1439 233 235 1007 1009 1630 1635 1297 1301 359 363 1559 1561 1918 1922 1160 1161 1374 1377 418 420 248 252 1826 1831 1051 1053 720 722 276 279 1516 1522 1638 1639 28 34 1392 1394 1867 1869 1030 1035 961 964 951 954 56...
output:
1538
result:
ok single line: '1538'
Test #115:
score: 0
Accepted
time: 2ms
memory: 3956kb
input:
1530 1057 6 333 334 1671 1672 855 856 237 238 429 430 172 173 1721 1722 784 785 485 486 771 772 1563 1564 781 784 852 854 510 511 754 755 1640 1641 1748 1749 152 153 1286 1287 1765 1766 483 484 1374 1375 1435 1436 1081 1082 1960 1961 1512 1513 1001 1002 1287 1288 1737 1738 1213 1214 901 902 271 272 ...
output:
1530
result:
ok single line: '1530'
Test #116:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
1852 95 2 1686 1687 1089 1090 1406 1407 1703 1704 270 271 124 125 1656 1657 1467 1468 1244 1245 198 199 720 721 240 241 954 955 1617 1618 1576 1577 693 694 887 888 1875 1876 65 66 210 211 972 973 60 61 1977 1978 1747 1748 88 89 1571 1572 1913 1914 959 960 978 979 1592 1593 160 161 911 912 1923 1924 ...
output:
1852
result:
ok single line: '1852'
Test #117:
score: 0
Accepted
time: 5ms
memory: 4108kb
input:
2000 2000 8 113542287 113542302 390186210 390186213 767610940 767610945 166969613 166969625 576186044 576186049 900919537 900919544 65847079 65847093 914274569 914274570 717871869 717871873 446375619 446375623 411070467 411070470 118697002 118697012 686550784 686550796 825791725 825791731 986657892 ...
output:
4000
result:
ok single line: '4000'
Test #118:
score: 0
Accepted
time: 6ms
memory: 4228kb
input:
2000 2000 5 323112971 323112977 625095129 625095132 724765420 724765421 63941016 63941019 914151487 914151492 984437587 984437595 208379851 208379858 839949614 839949623 928366669 928366671 561458859 561458867 972589960 972589964 576223356 576223364 739171385 739171390 663662925 663662932 525889027 ...
output:
4000
result:
ok single line: '4000'
Test #119:
score: 0
Accepted
time: 6ms
memory: 4172kb
input:
2000 2000 6 298171660 298171662 490725349 490725356 36304805 36304811 207802050 207802060 837587473 837587479 987183666 987183676 560955022 560955034 287590452 287590463 694565254 694565264 859529266 859529272 541494910 541494922 771349806 771349812 225787473 225787476 648584932 648584944 905255077 ...
output:
4000
result:
ok single line: '4000'
Test #120:
score: 0
Accepted
time: 2ms
memory: 4096kb
input:
1641 1376 22 377 378 697 698 693 694 210 211 1214 1216 1345 1346 846 847 1532 1533 1935 1937 1069 1070 1597 1598 318 319 1066 1067 886 887 1302 1303 1103 1105 631 632 1787 1788 1063 1064 1152 1154 227 228 351 352 1718 1719 754 755 238 239 651 652 704 705 601 602 1332 1333 1945 1946 421 422 1392 1393...
output:
1641
result:
ok single line: '1641'
Test #121:
score: 0
Accepted
time: 0ms
memory: 6024kb
input:
718 741 39 1263 1273 1019 1020 1202 1205 1105 1106 1194 1195 459 463 548 550 1821 1825 1853 1854 1664 1665 831 832 26 27 705 706 1832 1833 1466 1467 1438 1439 1841 1842 590 591 1981 1983 1310 1314 1850 1853 1978 1980 1948 1949 993 994 743 746 702 704 1748 1751 956 957 536 539 1694 1696 653 654 54 55...
output:
735
result:
ok single line: '735'
Test #122:
score: 0
Accepted
time: 2ms
memory: 4028kb
input:
1375 1578 67 427 428 14 15 1981 1982 1983 1984 1865 1866 1425 1426 1944 1945 1796 1798 1045 1046 705 706 870 871 184 185 1817 1818 591 592 1710 1711 1132 1133 782 783 902 903 1805 1806 1438 1439 1508 1510 620 621 1832 1833 594 596 1471 1472 645 646 432 434 1680 1681 8 9 1318 1319 1543 1544 977 978 1...
output:
1532
result:
ok single line: '1532'
Test #123:
score: 0
Accepted
time: 6ms
memory: 4188kb
input:
2000 2000 22 341868816 341868843 367155688 367155695 135493529 135493570 659841251 659841280 765819862 765819872 784722731 784722769 141544674 141544697 616625335 616625350 476905250 476905273 242349445 242349486 939296167 939296190 296381442 296381478 528751822 528751862 608293329 608293356 5822529...
output:
4000
result:
ok single line: '4000'
Test #124:
score: 0
Accepted
time: 6ms
memory: 4196kb
input:
2000 2000 39 927916622 927916697 325367766 325367794 856736217 856736254 536269830 536269853 10213264 10213320 525742332 525742365 286222090 286222105 967547156 967547227 725030525 725030576 934264787 934264801 572638578 572638600 236729969 236730024 628968602 628968676 100517630 100517639 985987837...
output:
4000
result:
ok single line: '4000'
Test #125:
score: 0
Accepted
time: 6ms
memory: 4260kb
input:
2000 2000 67 767187100 767187119 986940990 986941073 308695512 308695622 238031183 238031199 754701671 754701748 2519007 2519037 847920995 847921121 867519831 867519887 633569931 633570037 21505154 21505229 541253140 541253210 76904813 76904931 370362036 370362147 222364602 222364689 643428933 64342...
output:
4000
result:
ok single line: '4000'
Test #126:
score: 0
Accepted
time: 3ms
memory: 3984kb
input:
1801 1118 7 5008 5011 9388 9394 5853 5858 8470 8471 1273 1275 968 970 1583 1585 6999 7000 6626 6632 1362 1365 546 551 4540 4541 5756 5757 3236 3238 7883 7886 3451 3458 1186 1188 3646 3654 8632 8633 1676 1677 9121 9122 4981 4983 4869 4870 3329 3333 7979 7980 322 325 9441 9443 2033 2035 741 742 7317 7...
output:
2095
result:
ok single line: '2095'
Test #127:
score: 0
Accepted
time: 2ms
memory: 4032kb
input:
173 1328 4 6361 6362 8758 8760 1604 1612 5366 5368 3091 3099 8362 8367 8399 8406 2915 2920 1585 1591 9754 9758 5517 5525 5508 5510 5816 5823 3670 3672 3244 3245 7414 7418 1843 1845 9671 9679 2922 2926 9643 9645 2708 2712 5000 5003 180 181 1151 1152 5945 5950 6430 6435 8478 8481 4595 4603 1084 1090 2...
output:
1444
result:
ok single line: '1444'
Test #128:
score: 0
Accepted
time: 3ms
memory: 3936kb
input:
1344 1104 5 1879 1884 8042 8044 1512 1514 9729 9736 2229 2232 9974 9975 4335 4339 3631 3634 4816 4817 5661 5662 6275 6280 8797 8804 6347 6348 9244 9245 5884 5885 2314 2316 4341 4350 1109 1110 8190 8199 3209 3210 2266 2267 7240 7241 442 444 1650 1660 8626 8632 6517 6522 3564 3565 7379 7380 54 55 9592...
output:
1968
result:
ok single line: '1968'
Test #129:
score: 0
Accepted
time: 5ms
memory: 4216kb
input:
1801 1118 8818 299648146 299648921 634991862 634995510 17600292 17606666 584960465 584975652 605178662 605188921 136825738 136830581 468470295 468487515 812289237 812291890 908300607 908301000 371061746 371065020 637916467 637921315 791509404 791516878 579815394 579830764 165461681 165471358 3709745...
output:
2914
result:
ok single line: '2914'
Test #130:
score: 0
Accepted
time: 2ms
memory: 3984kb
input:
173 1328 504 789591864 789592603 419389263 419389465 631057151 631057560 793894508 793894560 733337608 733337946 347331803 347332760 406894159 406894174 377922914 377923695 850278166 850278984 966882383 966882891 40040418 40040511 431425356 431425613 339847101 339847278 661365924 661366278 20859765 ...
output:
1501
result:
ok single line: '1501'
Test #131:
score: 0
Accepted
time: 6ms
memory: 4120kb
input:
2000 2000 7984 339920481 339921279 225025481 225031390 368905241 368910451 859123005 859134183 229280199 229288499 13788323 13790692 454496099 454506465 705349718 705362443 312435440 312441025 471001714 471011731 583513429 583522612 828898408 828903187 337955186 337963628 546809371 546812177 9662249...
output:
3991
result:
ok single line: '3991'
Test #132:
score: 0
Accepted
time: 4ms
memory: 4108kb
input:
1477 1013 215799 820746965 820903972 235759939 235964519 927350766 927372711 441613567 441617616 223651883 223808949 451588249 451780490 537058997 537297402 980442214 980652302 339359130 339380069 814950455 815096407 123458370 123552031 577757858 578074582 209150551 209286637 679146135 679265919 862...
output:
2313
result:
ok single line: '2313'
Test #133:
score: 0
Accepted
time: 3ms
memory: 4020kb
input:
690 1275 103826 69978534 70044833 362562070 362617101 138568866 138737780 100792091 100903864 806054798 806210315 303203756 303214371 365107745 365189852 331126421 331275613 905525891 905527125 797188174 797320999 751853571 751990547 781606965 781665188 936696124 936808636 64417551 64428684 81940041...
output:
1927
result:
ok single line: '1927'
Test #134:
score: 0
Accepted
time: 6ms
memory: 4184kb
input:
2000 2000 238104 396195086 396200531 847207834 847332258 179994708 180280134 936637373 936637803 142798890 143169794 485081815 485105422 980224150 980253706 746341763 746420525 58384006 58500295 825594403 825910834 86660443 86662952 129714220 129807587 985730074 985738891 492676441 492860827 8601734...
output:
3429
result:
ok single line: '3429'
Test #135:
score: 0
Accepted
time: 4ms
memory: 4100kb
input:
2000 2000 840413426 245432126 245840266 820710817 821104962 399672634 399941306 193464621 193504820 22371266 22467427 208469456 208657256 243779942 243908247 598840393 598869355 485615359 486254153 22892035 23841416 822113439 822724655 429404275 429512297 422467661 423173061 347293788 347392975 8087...
output:
2000
result:
ok single line: '2000'
Test #136:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
1 1 1000000000 516542443 729841337 244428434 812275082
output:
1
result:
ok single line: '1'
Test #137:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
1 1 157846707 475798536 565048510 925017069 932822770
output:
2
result:
ok single line: '2'
Test #138:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1 950798221 8782268 789153107 355263574 830913501
output:
1
result:
ok single line: '1'
Test #139:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1 671388450 295587077 322796253 196014814 610531728
output:
1
result:
ok single line: '1'
Test #140:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
1 1 364785590 947989275 956495485 802397137 931606382
output:
1
result:
ok single line: '1'
Test #141:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
2 2 731145322 187729013 483416577 713971619 873645695 713631432 745397721 531149064 619687775
output:
2
result:
ok single line: '2'
Test #142:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
2 2 118961482 393921001 484808236 28918989 201556545 827862893 859953290 21806393 82884525
output:
3
result:
ok single line: '3'
Test #143:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 2 866022286 346503962 854690942 978283256 989458723 307988586 359532820 388575756 847032394
output:
2
result:
ok single line: '2'
Test #144:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
2 2 579190821 696013116 862318605 920027096 948189287 34511307 349337089 688888024 865627719
output:
2
result:
ok single line: '2'
Test #145:
score: 0
Accepted
time: 6ms
memory: 4124kb
input:
2000 2000 28457 380073308 380129124 337673316 337725490 328507761 328512801 80835174 80886619 506386553 506409956 449767860 449804796 729249984 729266202 280195213 280251651 309921700 309949789 168590985 168645214 553950166 553982841 870386267 870388775 841632890 841661301 115503002 115538714 623851...
output:
3953
result:
ok single line: '3953'
Test #146:
score: 0
Accepted
time: 6ms
memory: 4184kb
input:
2000 2000 256401 674503522 674530800 507904838 508414477 713869060 714061164 411783621 412081838 34060885 34255407 244482303 244549640 374806533 374863581 107557985 107939331 931987804 932274196 384456654 384494772 996331844 996356706 720269743 720570553 878985719 879227913 494035573 494213734 12066...
output:
3371
result:
ok single line: '3371'
Test #147:
score: 0
Accepted
time: 3ms
memory: 4128kb
input:
2000 2000 191323 608483839 608548210 440584583 440731206 122944325 123104690 994111553 994263026 522856060 522890155 219442124 219501599 8538966 8748323 949304216 949393487 177315835 177451353 314313734 314353881 407881410 408029302 962479115 962589734 498940105 498941336 735093209 735095084 7376835...
output:
3548
result:
ok single line: '3548'
Test #148:
score: 0
Accepted
time: 6ms
memory: 4196kb
input:
2000 2000 82111 815001816 815076652 646244157 646361382 62945198 63100281 651403764 651517305 330022446 330156800 557602579 557650791 203637679 203742643 936537983 936662233 362156394 362300631 621507302 621507982 553311750 553444349 500235685 500240539 817919163 818009223 334919155 334930575 925197...
output:
3821
result:
ok single line: '3821'
Test #149:
score: -6
Wrong Answer
time: 6ms
memory: 4264kb
input:
2000 2000 294760 571769883 571829761 768941839 768970823 763555200 763829761 616413956 616589623 753061171 753081450 855737523 855781281 996835306 997129662 374495408 375047231 734657466 734703873 987347700 987354200 818298781 818367789 725716484 725749323 424315835 424369262 22593232 22911537 33207...
output:
3290
result:
wrong answer 1st lines differ - expected: '3291', found: '3290'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%