QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#43015 | #4270. Double Attendance | ppavic# | 0 | 5ms | 6216kb | C++ | 1.7kb | 2022-08-05 17:42:23 | 2024-05-26 01:03:39 |
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[N][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 - 1);
v.PB(max(x - k, 0));
v.PB(max(y - k - 1, 0));
v.PB(max(y - k, 0));
}
for(int i = 0;i < m;i++){
int x, y; scanf("%d%d", &x, &y);
S[1].PB({x, y});
v.PB(x); v.PB(y - 1);
v.PB(max(x - k, 0));
v.PB(max(y - k - 1, 0));
v.PB(max(y - k, 0));
}
sort(S[0].begin(), S[0].end());
sort(S[1].begin(), S[1].end());
v.PB(0);
//for(int i = 0;i < 10;i++) v.PB(i);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), 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;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 3988kb
input:
3 1 8 10 20 100 101 20 21 15 25
output:
3
result:
ok single line: '3'
Test #2:
score: 5
Accepted
time: 1ms
memory: 3940kb
input:
1 5 3 1 100 1 2 2 3 3 4 4 5 5 6
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3852kb
input:
10 10 5 4 9 43 48 69 70 70 72 52 67 75 83 100 103 103 1501 10 27 28 40 5 7 27 29 30 39 40 42 42 45 67 80 0 5 45 59 10 20 22 23
output:
20
result:
wrong answer 1st lines differ - expected: '18', found: '20'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #104:
score: 6
Accepted
time: 0ms
memory: 3972kb
input:
1 1 1 0 1 0 1
output:
1
result:
ok single line: '1'
Test #105:
score: 6
Accepted
time: 1ms
memory: 3908kb
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: 6
Accepted
time: 5ms
memory: 4120kb
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: 6
Accepted
time: 4ms
memory: 4100kb
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: 6
Accepted
time: 3ms
memory: 4088kb
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: 6
Accepted
time: 3ms
memory: 4092kb
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: 6
Accepted
time: 4ms
memory: 6216kb
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: 6
Accepted
time: 3ms
memory: 4024kb
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: 6
Accepted
time: 2ms
memory: 4116kb
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: 6
Accepted
time: 2ms
memory: 3992kb
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: 6
Accepted
time: 1ms
memory: 3996kb
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: 6
Accepted
time: 2ms
memory: 4040kb
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: 6
Accepted
time: 1ms
memory: 4096kb
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: 6
Accepted
time: 5ms
memory: 4120kb
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: 6
Accepted
time: 5ms
memory: 4068kb
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: 6
Accepted
time: 5ms
memory: 4112kb
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: 6
Accepted
time: 2ms
memory: 4068kb
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: 6
Accepted
time: 1ms
memory: 3996kb
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: 6
Accepted
time: 0ms
memory: 4052kb
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: 6
Accepted
time: 5ms
memory: 6036kb
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: 6
Accepted
time: 2ms
memory: 4116kb
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: 6
Accepted
time: 5ms
memory: 4148kb
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
Wrong Answer
time: 3ms
memory: 4052kb
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:
2094
result:
wrong answer 1st lines differ - expected: '2095', found: '2094'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%