QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#374628#1415. SpyZhangYiDe100 ✓144ms248420kbC++202.3kb2024-04-02 15:56:482024-04-02 15:56:50

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 3ms
memory: 32256kb

input:

200 200
60 93
153 107
29 21
105 133
184 164
8 31
164 159
59 91
149 92
98 109
87 77
78 123
172 14
106 60
43 81
144 74
146 145
140 26
148 40
86 200
137 18
11 16
19 55
132 175
35 181
49 39
114 97
62 48
22 154
142 78
158 96
185 36
135 64
18 1
51 174
162 173
187 95
125 113
68 150
16 76
174 72
107 49
192 ...

output:

29
113
4
169
175
110
63
69
37
67
1
135
68
32
93
33
91
72
34
48
57
0
18
9
4
72
24
78
3
20
73
22
113
113
33
37
76
9
58
87
58
45
60
54
48
23
89
78
50
8
30
12
6
124
28
81
61
64
35
21
2
19
50
10
0
118
39
13
68
116
31
6
43
28
100
169
46
125
22
75
79
10
0
37
42
115
1
81
8
5
108
57
55
9
44
135
33
81
20
14
7...

result:

ok 200 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 28140kb

input:

200 200
170 182
69 193
109 26
194 199
15 143
8 89
27 141
193 36
191 191
50 185
149 58
152 174
96 93
173 12
21 69
32 122
6 157
62 38
167 195
110 66
63 132
89 194
171 104
123 39
22 131
115 75
52 144
71 8
102 149
107 124
112 102
26 18
48 20
124 178
16 145
7 72
192 9
196 70
120 50
197 43
28 35
98 3
195 ...

output:

200
200
200
200
200
200
197
200
195
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
174
200
200
200
200
200
200
200
200
200
199
200
200
200
200
200
200
200
200
200
200
200
200
200
200
132
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
200
...

result:

ok 200 lines

Test #3:

score: 0
Accepted
time: 4ms
memory: 29596kb

input:

200 200
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 165
194 ...

output:

53
53
52
52
52
52
52
52
53
52
52
53
52
53
52
53
53
53
53
52
52
53
52
53
52
54
53
52
52
52
54
56
52
52
53
54
53
53
52
53
52
52
52
52
52
52
52
52
52
53
52
53
52
53
54
53
53
52
53
52
52
53
53
52
53
53
52
52
53
52
53
52
52
52
56
52
52
53
52
52
53
53
52
56
53
54
53
52
52
53
54
53
52
52
52
52
53
52
54
53
...

result:

ok 200 lines

Test #4:

score: 0
Accepted
time: 4ms
memory: 30624kb

input:

200 200
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 155
175 ...

output:

86
87
86
86
86
87
86
86
87
86
86
87
87
88
86
86
86
88
87
89
86
86
87
86
88
88
87
87
86
86
86
87
86
86
86
88
86
87
87
87
87
87
86
86
87
88
86
87
86
86
86
86
86
87
86
86
86
86
88
86
86
88
86
86
86
87
88
86
86
86
87
86
86
86
86
86
86
87
87
86
88
87
87
87
87
86
88
88
86
86
86
86
86
86
86
86
87
88
88
86
...

result:

ok 200 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 30576kb

input:

200 200
103 42
110 7
47 189
88 16
67 109
191 5
56 112
181 20
25 159
188 61
83 53
31 198
29 88
40 109
42 92
46 200
112 58
97 15
154 38
199 137
190 80
82 8
115 48
83 103
107 164
168 61
146 39
21 34
66 122
59 167
167 171
0 79
61 125
159 2
154 187
69 116
13 113
112 11
194 97
133 54
48 165
107 76
96 159
...

output:

3
6
2
6
1
2
1
0
1
1
3
1
10
2
0
3
2
2
5
3
2
0
5
2
3
2
4
3
3
3
2
3
1
6
5
1
1
2
3
2
2
2
4
4
1
2
3
1
2
3
6
4
0
3
3
3
6
3
3
3
1
0
2
3
2
0
5
3
1
4
1
1
1
3
4
2
1
4
1
1
2
3
3
4
3
4
1
3
1
0
3
2
6
4
7
3
6
1
2
1
3
3
0
4
3
3
0
2
0
1
5
2
3
4
3
1
2
2
3
2
4
4
2
2
3
3
2
4
5
1
2
1
0
4
2
8
1
4
1
3
2
3
2
2
3
1
2
1
2
9...

result:

ok 200 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 30332kb

input:

200 200
23 11
125 38
192 111
62 56
47 73
1 105
175 75
139 12
34 183
69 36
10 121
92 122
36 21
168 165
27 67
154 148
63 63
118 84
182 26
50 124
39 81
184 3
0 69
16 48
134 87
178 172
95 30
176 117
108 126
83 76
76 182
45 177
120 99
132 192
149 168
184 35
182 15
110 107
68 138
85 134
167 52
74 14
65 68...

output:

113
120
121
121
120
119
120
120
120
120
119
120
120
120
120
121
119
119
120
120
120
121
96
120
121
120
119
121
119
119
119
121
120
121
120
120
120
120
121
118
119
120
120
119
119
120
119
120
121
121
121
121
120
120
120
121
119
120
121
119
119
120
119
121
120
120
120
120
119
121
119
119
120
119
120
1...

result:

ok 200 lines

Test #7:

score: 0
Accepted
time: 4ms
memory: 30348kb

input:

200 200
158 7
101 158
34 142
141 0
150 127
62 29
119 181
188 53
82 186
64 194
157 15
173 200
198 9
177 33
7 164
93 95
102 143
185 109
10 173
159 78
77 126
46 62
180 36
97 185
171 27
17 182
145 134
65 99
108 18
59 115
137 177
116 69
36 21
165 57
68 61
105 67
87 46
51 98
20 141
57 147
162 64
38 12
90 ...

output:

6
4
15
0
2
7
4
1
7
5
10
8
10
5
10
9
1
14
4
2
6
10
0
4
4
4
3
8
11
5
2
5
17
26
10
2
14
15
1
4
10
11
3
8
15
13
3
9
0
5
7
9
1
7
7
2
10
12
8
1
10
5
26
3
5
6
4
12
2
19
11
6
10
10
0
3
5
5
8
4
5
6
9
1
2
3
6
9
2
3
1
2
7
1
12
9
13
4
1
4
8
4
3
13
13
3
8
12
6
12
7
2
10
7
8
3
0
5
10
13
8
5
8
5
8
4
3
8
3
5
7
1
3
...

result:

ok 200 lines

Test #8:

score: 0
Accepted
time: 4ms
memory: 31548kb

input:

200 200
166 32
105 200
163 178
131 200
77 51
109 198
176 73
143 80
176 30
176 175
61 104
56 136
117 199
44 45
108 70
31 33
103 185
190 91
150 118
2 130
48 47
43 42
94 22
23 131
161 129
188 156
36 85
140 57
7 166
45 163
89 157
99 76
82 111
191 158
24 101
169 127
116 68
28 140
200 185
108 162
142 1
68...

output:

1
1
0
0
2
1
1
0
0
0
2
0
0
1
1
0
1
0
2
2
0
2
0
0
0
0
1
1
0
2
2
1
0
0
1
0
0
3
1
2
0
6
1
0
4
0
1
1
0
0
2
0
2
2
1
0
0
1
1
2
0
0
0
0
0
3
0
1
0
2
0
3
1
3
1
0
0
0
1
0
0
0
3
0
0
1
3
3
2
0
2
3
0
0
0
3
1
2
2
0
4
0
0
0
1
0
1
0
2
3
0
2
3
3
0
0
0
4
1
0
0
1
0
1
0
2
0
0
0
1
0
2
1
0
0
0
1
2
1
3
1
1
2
0
1
4
2
1
0
2
...

result:

ok 200 lines

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #9:

score: 20
Accepted
time: 51ms
memory: 248272kb

input:

2000 2000
1962 651
1758 1961
678 1122
519 844
1576 1555
1386 34
51 1945
1220 347
766 1272
663 1161
1305 1049
1931 1223
914 1104
508 1447
1542 567
340 995
562 1232
1082 1196
1142 748
649 1846
725 1000
112 248
1615 1942
576 236
1860 1420
1946 1466
1257 596
73 1711
1210 1698
452 1510
606 1195
919 1383
...

output:

475
536
1581
1205
323
356
76
1680
219
597
1699
13
33
116
125
284
699
38
892
115
540
98
899
1278
106
86
923
1255
323
1013
58
1172
640
23
1407
219
533
1094
204
178
290
485
152
180
1327
653
1167
1224
613
600
106
491
1836
329
1538
309
824
65
814
68
315
1478
123
931
540
991
1312
494
670
755
495
289
753
1...

result:

ok 2000 lines

Test #10:

score: 0
Accepted
time: 51ms
memory: 248148kb

input:

2000 2000
1008 569
10 2000
1777 945
946 1615
373 152
1841 603
920 1001
1625 182
1139 1897
591 1224
1812 1766
239 78
1452 147
1638 662
1545 1915
1617 717
1052 710
1089 1573
868 907
1414 297
1387 393
379 1467
293 538
1981 58
142 1975
1873 649
628 1136
1724 1952
725 465
1025 1074
1074 567
1593 368
758 ...

output:

2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
2000
...

result:

ok 2000 lines

Test #11:

score: 0
Accepted
time: 47ms
memory: 248400kb

input:

2000 2000
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
1906 316
19...

output:

506
508
508
508
506
507
507
507
508
506
506
506
507
507
507
506
507
507
507
508
508
506
508
509
506
507
507
508
508
506
508
506
507
507
506
506
507
507
507
507
507
509
506
507
508
506
506
506
507
506
506
507
508
506
506
507
507
506
508
506
506
506
506
506
506
506
508
507
506
509
506
507
506
507
506
...

result:

ok 2000 lines

Test #12:

score: 0
Accepted
time: 44ms
memory: 248172kb

input:

2000 2000
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
843 182
84...

output:

921
919
919
920
919
919
919
919
920
919
919
919
920
919
920
919
919
919
920
919
919
919
919
919
920
920
919
920
919
920
919
919
919
919
919
919
919
922
919
922
921
920
919
919
919
919
920
919
919
919
919
919
919
919
920
919
919
919
919
919
919
919
919
920
919
919
919
920
919
920
920
919
919
919
920
...

result:

ok 2000 lines

Test #13:

score: 0
Accepted
time: 44ms
memory: 248164kb

input:

2000 2000
510 207
273 1815
81 1518
1060 159
264 908
611 162
424 1142
106 14
1174 736
1186 1439
1725 685
1215 679
1938 715
967 1123
1114 1595
995 861
1578 593
1809 1297
1346 231
808 360
425 1666
302 778
621 1390
1720 1416
898 697
131 1167
294 232
1551 1629
603 1854
34 1984
311 1012
1324 47
1850 85
14...

output:

1
0
1
1
1
3
1
0
0
2
4
3
0
0
2
1
0
0
2
0
1
0
2
3
2
1
1
0
1
1
3
2
0
1
3
0
2
3
0
1
0
0
0
2
3
2
2
0
3
3
2
4
0
2
1
0
2
2
1
0
0
0
1
4
3
0
0
2
3
4
1
1
0
0
0
5
1
4
1
1
0
1
1
0
1
0
1
2
0
2
0
1
0
2
2
2
1
0
0
0
2
0
2
1
2
2
1
2
3
1
4
1
3
3
1
3
1
2
2
1
2
0
0
1
1
1
3
2
1
3
1
2
0
0
3
0
1
1
1
1
1
2
3
4
0
1
1
2
1
1
...

result:

ok 2000 lines

Test #14:

score: 0
Accepted
time: 59ms
memory: 248152kb

input:

2000 2000
1653 16
27 607
1083 858
1359 1593
110 40
1367 1805
1092 440
1399 252
1360 1953
661 1751
1598 122
1785 1163
1927 1442
156 1921
1997 1373
288 573
316 202
921 890
1959 100
855 561
860 184
1021 1510
489 696
770 1080
655 1828
363 300
826 1276
0 1953
1189 1601
218 424
706 1574
108 1036
1413 1515...

output:

1320
1323
1353
1349
1321
1321
1313
1325
1316
1323
1310
1328
1320
1311
1333
1351
1321
1325
1310
1351
1349
1321
1310
1353
1328
1321
1313
1119
1344
1329
1329
1313
1325
1328
1315
1314
1331
1352
1307
1349
1309
1310
1325
1314
1349
1345
1314
1328
1325
1323
1314
1321
1320
1312
1321
1321
1328
1314
1321
1314
...

result:

ok 2000 lines

Test #15:

score: 0
Accepted
time: 44ms
memory: 248420kb

input:

2000 2000
1872 1270
1435 657
84 168
153 1326
1446 1658
1491 1621
698 1717
148 413
1635 762
97 1761
641 452
882 1496
1346 988
929 791
621 1731
1609 1593
1137 643
609 531
1775 119
1590 1461
449 477
1342 907
1393 763
358 926
289 498
1496 1975
344 1484
716 1595
113 1273
261 698
819 377
1636 1476
1934 17...

output:

29
18
29
10
24
18
11
53
14
29
29
12
15
3
6
2
29
11
17
30
19
27
20
3
0
24
48
15
4
18
44
6
25
6
7
1
13
0
0
3
0
1
7
42
0
15
3
10
24
19
7
21
20
61
24
3
8
8
7
3
20
42
33
4
29
9
27
77
14
44
36
22
63
20
35
7
30
33
31
31
9
11
36
7
1
0
60
17
4
41
7
9
12
47
22
24
13
36
4
8
11
15
34
25
23
19
8
4
3
11
9
14
7
13...

result:

ok 2000 lines

Test #16:

score: 0
Accepted
time: 51ms
memory: 248196kb

input:

2000 2000
1018 399
1564 551
778 101
61 1215
403 1019
1230 489
1940 852
1574 1163
410 702
327 1161
508 788
98 954
1994 252
1841 1811
1408 1983
606 1009
108 466
279 942
1419 402
1198 1878
82 1771
451 1654
1551 1086
689 652
1334 994
831 452
351 1425
996 690
199 172
1346 130
699 1642
380 1383
1401 1073
...

output:

0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
2
0
0
1
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
0
0
1
0
1
0
1
1
0
0
0
1
0
0
0
0
...

result:

ok 2000 lines

Subtask #3:

score: 70
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 70
Accepted
time: 144ms
memory: 248368kb

input:

2000 500000
326 1137
696 1911
525 1048
342 815
1573 1271
1246 455
19 1612
651 360
1474 254
1297 982
759 1331
509 773
869 1478
356 1082
771 1201
804 1198
1305 1304
42 34
473 1276
1704 87
470 1590
1210 1119
1659 1541
294 727
1520 1071
1993 594
1115 1027
321 798
351 167
268 436
1976 1770
1165 1063
485 ...

output:

100762
93491
230711
97001
53999
85930
1245
25253
32967
79233
66623
20691
77990
418497
42913
192589
226961
54267
201693
92372
64984
10428
12975
279610
149167
104203
73883
4692
38896
147297
270827
107723
7230
123918
160632
59502
449740
192066
3872
84887
12295
29901
321628
348681
14689
369920
125534
26...

result:

ok 2000 lines

Test #18:

score: 0
Accepted
time: 75ms
memory: 248360kb

input:

2000 500000
853 1166
1850 370
1552 30
1959 734
1200 1102
1945 1479
983 435
659 1137
374 216
1163 586
625 1944
1474 1695
1308 1766
1162 556
202 425
283 1269
89 1913
1171 659
526 156
1946 795
1231 252
1954 301
679 1287
900 1552
1319 1259
1252 1511
774 998
3 604
211 1299
725 562
1689 1039
1476 175
748 ...

output:

500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000
500000...

result:

ok 2000 lines

Test #19:

score: 0
Accepted
time: 119ms
memory: 248236kb

input:

2000 500000
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
899 1750
...

output:

125345
125344
125332
125343
125369
125335
125362
125369
125354
125352
125329
125362
125334
125342
125335
125348
125338
125334
125360
125343
125348
125352
125317
125333
125328
125327
125337
125330
125332
125345
125357
125330
125353
125349
125321
125353
125336
125328
125338
125355
125362
125324
125374...

result:

ok 2000 lines

Test #20:

score: 0
Accepted
time: 130ms
memory: 248168kb

input:

2000 500000
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 1308
1139 130...

output:

222006
221986
221987
221985
221981
221989
221966
221971
221986
221981
221981
221978
221978
221989
221987
221992
221987
221969
221978
221983
221992
221981
221991
221976
221986
221994
222011
221992
221970
221979
221999
221992
221980
221991
221993
221980
221985
221996
221985
221994
221971
221978
221992...

result:

ok 2000 lines

Test #21:

score: 0
Accepted
time: 142ms
memory: 248280kb

input:

2000 500000
54 217
1748 862
1025 46
520 688
2 576
1489 1037
238 931
1954 957
768 1974
682 236
561 1469
595 1910
1432 139
1077 130
433 1075
197 88
129 1376
487 420
1619 1812
1387 1999
60 1818
108 1444
2 299
754 1604
1650 1538
503 68
697 100
565 798
479 599
763 1932
335 1271
1543 713
1666 1237
320 139...

output:

472
355
348
344
407
395
518
370
343
885
395
507
381
387
385
448
374
389
383
578
417
521
362
415
454
436
504
589
341
416
310
369
442
373
418
317
379
370
584
436
414
398
361
357
453
312
279
430
435
351
384
377
475
686
398
398
356
407
338
479
420
335
443
339
471
698
346
314
396
343
451
592
522
396
478
...

result:

ok 2000 lines

Test #22:

score: 0
Accepted
time: 82ms
memory: 248388kb

input:

2000 500000
876 1782
7 607
1155 1014
395 967
1098 785
1363 883
1063 1350
894 981
625 720
473 1886
524 479
1261 558
636 1267
517 270
1867 686
1709 885
369 1918
535 85
1713 194
1940 1078
1999 802
1323 1372
1859 1987
658 1341
1908 1700
384 1335
554 1904
365 1877
1336 1622
1990 443
1572 736
139 1888
702...

output:

319490
319488
319533
310598
319551
319533
319447
319552
319516
319482
319465
319559
319464
319485
319546
319549
319532
319547
319488
319549
319529
319613
319532
319611
319554
319525
319530
318077
319532
319490
319535
319558
319546
319481
319422
319533
319557
319547
319557
319481
319536
319489
319551...

result:

ok 2000 lines

Test #23:

score: 0
Accepted
time: 143ms
memory: 248144kb

input:

2000 500000
571 261
1022 542
925 1525
1492 214
195 1775
751 1089
535 1893
582 729
914 137
363 933
770 693
74 228
1165 535
419 308
567 780
673 1182
524 1051
171 428
1532 1948
1582 1157
1134 504
1988 1781
1191 686
768 998
1281 1641
1566 1315
532 820
1600 542
1586 495
1531 1433
1043 320
1187 851
489 35...

output:

1512
107
1912
6054
928
3141
4690
1502
1085
1280
395
4750
1129
1941
2019
646
2422
1555
1759
1049
558
1829
505
4306
2566
623
746
22
2787
1681
1344
657
834
2411
739
2036
3754
2069
838
2187
2308
2535
8389
1463
1712
1565
3388
2396
264
3666
2667
634
1556
1275
354
3118
3812
3266
2578
871
224
804
902
2442
1...

result:

ok 2000 lines

Test #24:

score: 0
Accepted
time: 139ms
memory: 248216kb

input:

2000 500000
960 211
868 465
964 1746
916 1488
189 1953
1788 1015
227 407
1411 1971
912 412
148 1673
568 1509
1674 1068
1439 89
632 125
151 531
170 798
1837 365
758 1520
1818 938
736 1735
408 729
265 334
1321 458
1324 630
168 894
454 28
1946 1699
1307 1574
1370 1173
464 1095
222 1241
1572 548
1244 19...

output:

128
107
58
111
34
39
26
36
58
32
33
29
57
46
63
52
20
66
85
21
102
86
39
67
33
34
29
82
91
61
14
29
56
29
23
23
45
37
133
71
21
32
62
60
94
21
39
43
24
124
41
57
28
24
62
98
70
21
59
76
4
72
30
89
19
36
88
37
58
32
24
51
38
38
66
34
18
17
32
93
19
83
26
24
92
33
105
4
44
53
33
18
86
39
35
33
8
29
86...

result:

ok 2000 lines

Test #25:

score: 0
Accepted
time: 1ms
memory: 5808kb

input:

1 1
0 0
1 1

output:

1

result:

ok single line: '1'

Extra Test:

score: 0
Extra Test Passed