QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#43015#4270. Double Attendanceppavic#0 5ms6216kbC++1.7kb2022-08-05 17:42:232024-05-26 01:03:39

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 01:03:39]
  • 评测
  • 测评结果:0
  • 用时:5ms
  • 内存:6216kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-05 17:42:23]
  • 提交

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%