QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #20338 | #2424. The short shank; Redemption | linmuhan# | 100 ✓ | 426ms | 164580kb | C++20 | 2.0kb | 2022-02-15 17:00:48 | 2022-05-03 09:39:27 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2000010, UPS = 1000000000;
int n, D, T;
int t[N], l[N];
int st[N], top = 0;
int Ans = 0;
struct inter {
int l, r;
}b[N]; int tot = 0;
bool cmp (inter p, inter q) {
if (p.r != q.r) return p.r < q.r;
else return p.l > q.l;
}
struct edge {
int to, nxt;
}e[N];
int head[N], cnt, in[N], dep[N], mxdp[N], son[N];
priority_queue <int> pq;
void add (int u, int v) {
cnt ++;
e[cnt].to = v; in[v] ++;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs (int u) {
for (int i=head[u];i;i=e[i].nxt) {
int v = e[i].to;
dep[v] = dep[u] + 1;
dfs (v);
mxdp[u] = max (mxdp[u], mxdp[v]);
if (mxdp[u] == mxdp[v]) son[u] = v;
}
mxdp[u] ++;
}
void linke (int u, int dep) {
if (! son[u]) pq.push (dep);
if (son[u]) linke (son[u], dep + 1);
for (int i=head[u];i;i=e[i].nxt) {
int v = e[i].to;
if (v == son[u]) continue ;
linke (v, 1);
}
}
int main () {
scanf ("%d %d %d", &n, &D, &T); Ans = n;
for (int i=1;i<=n;i++) scanf ("%d", &t[i]), l[i] = -1;
for (int i=1;i<=n;i++) {
if (! top) l[i] = -1;
else {
int L = 1, R = top;
while (L <= R) {
int mid = (L + R) >> 1;
if (T + st[mid] - t[st[mid]] >= i) l[i] = st[mid], L = mid + 1;
else R = mid - 1;
}
}
while (top && T + i - t[i] > T + st[top] - t[st[top]]) top --;
st[++ top] = i;
}
for (int i=1;i<=n;i++) {
if (l[i] == -1 || t[i] <= T) {
if (t[i] > T) Ans --;
} else {
b[++ tot] = (inter) {l[i], i};
}
}
sort (b + 1, b + tot + 1, cmp); top = 0;
for (int i=1;i<=tot;i++) {
while (top && b[st[top]].l >= b[i].l && b[st[top]].r <= b[i].r) add (i, st[top]), top --;
st[++ top] = i;
}
for (int i=1;i<=tot;i++) if (! in[i]) dep[i] = 1, dfs (i);
for (int i=1;i<=tot;i++) if (! in[i]) linke (i, 1);
// for (int i=1;i<=tot;i++) cout << mxdp[i] << " "; puts ("");
// cout << Ans << endl;
for (int i=1;i<=D&&pq.size();i++) Ans -= pq.top (), pq.pop ();
cout << Ans << endl;
}
详细
Subtask #1:
score: 0
Accepted
Test #1:
score: 0
Accepted
time: 4ms
memory: 7904kb
input:
5 1 42 13 37 47 11 42
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7852kb
input:
5 2 5 1 9 4 6 7
output:
2
result:
ok single line: '2'
Subtask #2:
score: 15
Accepted
Dependency #1:
100%
Accepted
Test #3:
score: 15
Accepted
time: 0ms
memory: 7796kb
input:
6 1 10 8 11 11 1 11 11
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7884kb
input:
410 10 461244987 100628539 280438144 678842284 572394726 16730300 671693589 36221156 510097048 573559942 31857089 514611025 187449268 737079253 110882506 87278298 642600230 461696671 112278571 888853308 730176938 594447854 846956812 339223493 538813410 767621075 666806803 804854891 355452047 5336811...
output:
348
result:
ok single line: '348'
Test #5:
score: 0
Accepted
time: 4ms
memory: 7716kb
input:
410 20 467139057 467138601 467138805 467138443 467139774 467138082 467139774 467139287 467139903 467139929 467138874 467138791 467138613 467139958 467140403 467138925 467138921 467139958 467138471 467139184 467138567 467139329 467139842 467139841 467139407 467139370 467137840 467138401 467139248 467...
output:
333
result:
ok single line: '333'
Test #6:
score: 0
Accepted
time: 0ms
memory: 7764kb
input:
500 50 538420782 373329753 904027309 995408659 742704129 647828090 671731260 484389120 554182278 342065655 190294193 667434431 452939685 186453440 891622807 795439666 148575048 435108242 310497660 454721287 951642681 471453570 443525881 489334576 124182147 790427831 930290207 774778273 921000780 638...
output:
343
result:
ok single line: '343'
Test #7:
score: 0
Accepted
time: 4ms
memory: 7724kb
input:
500 99 493693293 493693463 493693235 493692329 493693706 493693265 493693270 493693295 493693669 493693215 493694444 493692238 493693625 493693468 493693598 493693765 493692645 493694370 493692899 493693953 493692418 493692461 493693261 493693466 493691941 493694440 493693937 493692427 493693786 493...
output:
251
result:
ok single line: '251'
Test #8:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
500 3 346 7 347 347 347 17 347 20 17 347 19 29 25 347 29 32 347 37 347 42 47 347 347 347 347 347 347 58 347 347 347 68 347 67 347 347 347 74 347 347 347 347 90 86 347 347 347 96 347 105 347 105 111 106 347 109 347 117 347 347 125 347 125 347 135 347 138 140 347 347 147 141 145 153 347 152 156 347 16...
output:
333
result:
ok single line: '333'
Test #9:
score: 0
Accepted
time: 1ms
memory: 7860kb
input:
500 40 18 7 19 19 19 17 19 20 17 19 3 13 9 19 13 16 19 21 19 26 31 19 19 19 19 19 10 19 19 19 20 19 19 19 19 19 7 19 19 19 16 12 19 19 6 19 15 19 15 21 16 19 19 19 27 19 19 11 19 11 19 21 19 24 26 19 19 33 27 31 39 19 4 19 19 12 12 19 19 19 6 5 7 9 14 11 19 19 19 27 4 19 19 14 10 15 19 19 19 19 25 2...
output:
178
result:
ok single line: '178'
Test #10:
score: 0
Accepted
time: 4ms
memory: 7772kb
input:
500 10 1456 1349 1951 2280 1819 2009 2403 1715 2882 1454 1734 1455 2768 1843 2535 2656 2063 2233 1661 2177 2374 2131 1453 2298 1857 1452 2646 2367 2445 1455 2167 1452 2271 1949 2388 1454 1960 1454 2403 1454 1830 2266 2721 2831 2117 1451 1794 2834 1453 2278 1455 2782 2455 2316 2218 1917 1454 1962 145...
output:
313
result:
ok single line: '313'
Test #11:
score: 0
Accepted
time: 2ms
memory: 7776kb
input:
500 20 1456 2904 2191 2586 2260 2021 1906 2806 1692 2631 1819 1220 2176 1942 2204 2731 1985 1452 2401 1453 2481 1453 2428 1454 1704 2648 1453 1874 2517 1636 2399 2257 1862 1451 1511 1453 1820 2551 1453 2218 1939 1454 2912 1452 2398 2753 1457 2379 1455 2126 1467 2327 2330 1870 2250 2904 1452 2378 241...
output:
268
result:
ok single line: '268'
Test #12:
score: 0
Accepted
time: 4ms
memory: 7776kb
input:
500 50 1456 2536 2354 1621 2277 2070 2504 2397 2565 1850 2198 2387 1606 2814 2693 1583 2177 1944 1964 2745 2763 2793 2614 1908 2315 1528 2468 2705 1202 2474 2193 1454 2170 1452 2249 1452 2351 1452 2667 1450 1809 2437 1493 2399 2562 2755 2314 2496 2306 2860 2652 1453 1619 1453 2893 1768 2727 2043 240...
output:
188
result:
ok single line: '188'
Test #13:
score: 0
Accepted
time: 0ms
memory: 7804kb
input:
500 99 1456 2617 1687 2849 2451 2336 2840 1796 1358 2360 1454 2016 2671 1452 1779 2170 1453 2424 2126 1452 2147 2196 2203 1452 2253 1455 2521 2418 1451 2514 2878 1453 2278 2035 1454 2327 1979 1604 2842 2131 2755 2105 2425 2695 1453 2711 1452 1817 2660 2341 1451 1858 2107 2772 1617 1453 2302 1455 202...
output:
167
result:
ok single line: '167'
Subtask #3:
score: 10
Accepted
Test #14:
score: 10
Accepted
time: 2ms
memory: 7764kb
input:
6 1 10 8 11 11 1 11 11
output:
4
result:
ok single line: '4'
Test #15:
score: 0
Accepted
time: 101ms
memory: 18264kb
input:
500000 1 591811159 591879011 589913782 591320073 592236485 590803427 591682322 591927370 592117793 591259593 591580363 591886306 590055513 592922674 592908718 591830213 592512993 592034185 591578214 591954858 593556468 592008412 591003444 592139936 591209982 592739785 592308295 592151302 591662651 5...
output:
499979
result:
ok single line: '499979'
Test #16:
score: 0
Accepted
time: 82ms
memory: 15748kb
input:
500000 1 658345468 594329230 202848312 117536044 836200320 383763141 230086492 337732597 511795794 983983589 457804090 847880661 644949069 713055099 6023976 360758820 378566936 730088551 211675298 757155842 249349786 552536670 382709167 815660475 719452367 94091967 657565754 360058037 946759900 4425...
output:
499990
result:
ok single line: '499990'
Test #17:
score: 0
Accepted
time: 94ms
memory: 20276kb
input:
500000 1 697942 7 697943 697943 697943 17 697943 20 17 697943 19 29 25 697943 29 32 697943 37 697943 42 47 697943 697943 697943 697943 697943 697943 58 697943 697943 697943 68 697943 67 697943 697943 697943 74 697943 697943 697943 697943 90 86 697943 697943 697943 96 697943 105 697943 105 111 106 69...
output:
470809
result:
ok single line: '470809'
Test #18:
score: 0
Accepted
time: 64ms
memory: 22132kb
input:
500000 1 172 7 173 173 173 17 173 20 17 173 19 29 25 173 29 32 173 37 173 42 47 173 173 173 173 173 173 58 173 173 173 68 173 67 173 173 173 74 173 173 173 173 90 86 173 173 173 96 173 105 173 105 111 106 173 109 173 117 173 173 125 173 125 173 135 173 138 140 173 173 147 141 145 153 173 152 156 173...
output:
484530
result:
ok single line: '484530'
Test #19:
score: 0
Accepted
time: 96ms
memory: 21152kb
input:
500000 1 2788662 4965322 4869284 2798151 3635530 5303562 3408674 3347454 3286586 3317730 3529042 4291651 4805461 3290305 4173876 3536040 4197202 2915020 3793658 5362568 3048769 3854313 2890848 5200506 3230718 3895739 3814293 5037014 2837790 2937296 5209596 4114701 5113956 4501555 3910282 3172161 401...
output:
272994
result:
ok single line: '272994'
Test #20:
score: 0
Accepted
time: 106ms
memory: 60216kb
input:
500000 1 2788662 4097380 5470920 3406659 3357564 2989163 2964005 5413811 3204333 3778401 5504666 3365829 4189150 4143929 5431196 4583069 2800253 5406708 4029404 5540317 3875493 5377847 5475592 4176007 5182636 3545143 3411219 4358038 3450978 4264513 3040834 3149358 5573230 5509184 3553446 3139562 292...
output:
799
result:
ok single line: '799'
Test #21:
score: 0
Accepted
time: 69ms
memory: 21800kb
input:
500000 1 2788662 3963829 4504235 3457130 3433360 3099711 5232917 3426988 5194452 5530104 3561896 5266096 5190792 2862675 3063316 3450771 4358591 4393271 4733343 3454075 5091792 4312577 3286567 5501804 4587181 3106886 5265381 4603938 5374757 3485173 3144158 2789757 4446431 4859730 3458224 4877220 495...
output:
342417
result:
ok single line: '342417'
Subtask #4:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #22:
score: 20
Accepted
time: 5ms
memory: 7944kb
input:
4000 100 379545700 531059671 789043696 456086291 801707224 172489357 190682309 621309037 776674215 476995316 515935035 514774844 526482873 138591561 802873240 940651115 522037204 571918472 30455178 653354143 276671570 860679797 88077738 852805514 222921316 963894437 973362850 62228751 292554110 2106...
output:
3271
result:
ok single line: '3271'
Test #23:
score: 0
Accepted
time: 2ms
memory: 8004kb
input:
4000 200 410604329 410603446 410594735 410605804 410594402 410611753 410610141 410597392 410606237 410603695 410604843 410610733 410608410 410601346 410602073 410604059 410598456 410603306 410608513 410612853 410596572 410611965 410603938 410606224 410604896 410610848 410604916 410597659 410596889 4...
output:
3120
result:
ok single line: '3120'
Test #24:
score: 0
Accepted
time: 2ms
memory: 7940kb
input:
4000 300 379545700 531059671 789043696 456086291 801707224 172489357 190682309 621309037 776674215 476995316 515935035 514774844 526482873 138591561 802873240 940651115 522037204 571918472 30455178 653354143 276671570 860679797 88077738 852805514 222921316 963894437 973362850 62228751 292554110 2106...
output:
2491
result:
ok single line: '2491'
Test #25:
score: 0
Accepted
time: 2ms
memory: 7936kb
input:
4000 400 410604329 410603446 410594735 410605804 410594402 410611753 410610141 410597392 410606237 410603695 410604843 410610733 410608410 410601346 410602073 410604059 410598456 410603306 410608513 410612853 410596572 410611965 410603938 410606224 410604896 410610848 410604916 410597659 410596889 4...
output:
2668
result:
ok single line: '2668'
Test #26:
score: 0
Accepted
time: 5ms
memory: 7848kb
input:
4000 500 379545700 531059671 789043696 456086291 801707224 172489357 190682309 621309037 776674215 476995316 515935035 514774844 526482873 138591561 802873240 940651115 522037204 571918472 30455178 653354143 276671570 860679797 88077738 852805514 222921316 963894437 973362850 62228751 292554110 2106...
output:
2016
result:
ok single line: '2016'
Test #27:
score: 0
Accepted
time: 0ms
memory: 7840kb
input:
4000 60 410604329 410603446 410594735 410605804 410594402 410611753 410610141 410597392 410606237 410603695 410604843 410610733 410608410 410601346 410602073 410604059 410598456 410603306 410608513 410612853 410596572 410611965 410603938 410606224 410604896 410610848 410604916 410597659 410596889 41...
output:
3623
result:
ok single line: '3623'
Test #28:
score: 0
Accepted
time: 0ms
memory: 7944kb
input:
4000 70 379545700 531059671 789043696 456086291 801707224 172489357 190682309 621309037 776674215 476995316 515935035 514774844 526482873 138591561 802873240 940651115 522037204 571918472 30455178 653354143 276671570 860679797 88077738 852805514 222921316 963894437 973362850 62228751 292554110 21063...
output:
3448
result:
ok single line: '3448'
Test #29:
score: 0
Accepted
time: 4ms
memory: 7848kb
input:
4000 120 27174 28268 40128 33223 38028 41909 45991 27996 48570 29623 32830 32161 35484 43761 40691 53453 32402 47180 34594 42439 46401 39901 52309 46612 50101 40703 44858 37366 51029 44427 35304 40489 41570 44307 42587 52423 27918 30280 53244 49313 28778 31726 54299 37087 44362 36691 32241 45639 527...
output:
1997
result:
ok single line: '1997'
Test #30:
score: 0
Accepted
time: 2ms
memory: 7752kb
input:
4000 250 27174 48087 29148 48573 53853 54022 46793 39194 44927 30382 47208 52342 36997 44191 53807 53022 44013 30825 27819 39970 44008 36717 46844 31986 53344 41476 46319 48219 31284 42819 47757 41367 36557 45780 35592 32111 41504 28036 44130 32082 31243 36989 53299 41065 50055 48807 35788 39719 524...
output:
1660
result:
ok single line: '1660'
Test #31:
score: 0
Accepted
time: 3ms
memory: 7908kb
input:
4000 120 27174 52775 41639 32608 35713 33023 32761 32825 47327 36658 36046 41266 39768 27482 51265 53441 26644 27585 27173 48954 27173 37903 27173 48688 27172 28745 27173 41915 27173 31190 27173 36526 27120 47429 27173 47631 27173 39837 27173 39540 27170 53718 27173 36456 27173 33970 27173 53840 271...
output:
3210
result:
ok single line: '3210'
Test #32:
score: 0
Accepted
time: 5ms
memory: 7824kb
input:
4000 120 27174 50500 43416 26351 53413 27173 39749 27173 30933 27173 52056 27159 30643 27173 28777 27173 36424 27173 43823 27166 33825 27173 44052 27173 47912 27173 49820 27171 35561 27173 44986 27173 49181 27173 29870 27172 52101 27173 28535 27173 30007 27173 53682 27172 50050 27173 33694 27173 464...
output:
3210
result:
ok single line: '3210'
Test #33:
score: 0
Accepted
time: 5ms
memory: 8028kb
input:
4000 50 172 7 173 173 173 17 173 20 17 173 19 29 25 173 29 32 173 37 173 42 47 173 173 173 173 173 173 58 173 173 173 68 173 67 173 173 173 74 173 173 173 173 90 86 173 173 173 96 173 105 173 105 111 106 173 109 173 117 173 173 125 173 125 173 135 173 138 140 173 173 147 141 145 153 173 152 156 173 ...
output:
2502
result:
ok single line: '2502'
Test #34:
score: 0
Accepted
time: 5ms
memory: 7984kb
input:
4000 500 3250 7 3251 3251 3251 17 3251 20 17 3251 19 29 25 3251 29 32 3251 37 3251 42 47 3251 3251 3251 3251 3251 3251 58 3251 3251 3251 68 3251 67 3251 3251 3251 74 3251 3251 3251 3251 90 86 3251 3251 3251 96 3251 105 3251 105 111 106 3251 109 3251 117 3251 3251 125 3251 125 3251 135 3251 138 140 3...
output:
1896
result:
ok single line: '1896'
Subtask #5:
score: 10
Accepted
Test #35:
score: 10
Accepted
time: 6ms
memory: 7840kb
input:
6 1 10 8 11 11 1 11 11
output:
4
result:
ok single line: '4'
Test #36:
score: 0
Accepted
time: 24ms
memory: 9788kb
input:
75000 15 379160194 983631470 108027813 136568088 173091450 837382407 747957889 336100563 788603902 777030535 154707291 176290228 212903016 798222424 40621732 923070015 654829623 812160177 574453132 927566738 537451505 356478980 245566202 693863833 221722967 649023502 159900885 635583455 569510314 17...
output:
74734
result:
ok single line: '74734'
Test #37:
score: 0
Accepted
time: 14ms
memory: 9236kb
input:
75000 15 379160194 379210904 379130665 379178384 379064420 379149096 379093737 379150954 378937431 379165776 379021085 379079119 379159918 379177440 379221709 378964495 379122355 379274660 378983991 379061840 379065825 379340829 379083945 379030739 379260358 379128199 379184728 379217768 379070037 3...
output:
74831
result:
ok single line: '74831'
Test #38:
score: 0
Accepted
time: 16ms
memory: 12100kb
input:
75000 15 68642 4 68643 68643 68643 10 18 68643 68643 17 20 68643 68643 30 35 30 68643 38 41 68643 68643 68643 46 68643 68643 52 68643 55 63 61 68643 68 66 68643 68643 70 68643 75 83 81 68643 87 87 90 91 68643 68643 99 68643 97 68643 68643 108 68643 68643 113 68643 115 117 119 68643 68643 124 68643 6...
output:
34154
result:
ok single line: '34154'
Test #39:
score: 0
Accepted
time: 24ms
memory: 12968kb
input:
75000 15 500000000 499925000 499925003 499925006 499925010 499925014 499925017 499925020 499925022 499925028 499925029 499925032 499925038 499925036 499925041 499925046 499925048 499925049 499925051 499925054 499925061 499925069 499925070 499925070 499925076 499925084 499925076 499925087 499925081 4...
output:
24540
result:
ok single line: '24540'
Test #40:
score: 0
Accepted
time: 13ms
memory: 13224kb
input:
75000 15 500000000 499925000 499925003 499925009 499925013 499925012 499925018 499925022 499925027 499925029 499925027 499925035 499925034 499925047 499925042 499925058 499925061 499925051 499925061 499925072 499925068 499925071 499925085 499925068 499925071 499925078 499925083 499925083 499925115 4...
output:
24211
result:
ok single line: '24211'
Test #41:
score: 0
Accepted
time: 16ms
memory: 9564kb
input:
75000 15 309572 340213 343569 374670 362593 333900 357810 398477 380850 455393 559846 379243 361279 489886 486012 328212 370599 510233 531601 346322 315847 452744 355493 544714 480362 502817 418972 560602 560565 335750 402438 501001 366391 453751 583414 436727 495394 322080 525631 566671 485216 4663...
output:
34039
result:
ok single line: '34039'
Test #42:
score: 0
Accepted
time: 9ms
memory: 9624kb
input:
75000 15 309572 554928 420449 574187 465357 559302 485360 315848 613746 428494 350145 490002 522359 466882 495093 334102 348609 577315 345218 454161 360109 514813 380038 402089 356729 443804 557931 440418 572811 410772 326477 429545 346555 454669 384588 502339 412143 577691 525930 424060 387040 5665...
output:
32924
result:
ok single line: '32924'
Test #43:
score: 0
Accepted
time: 13ms
memory: 15352kb
input:
75000 15 309572 366502 611622 607024 352643 325982 456500 578910 316526 602768 510527 495725 452449 313828 360104 580328 609653 532434 518622 331856 502747 461998 360951 516495 234426 507099 433935 484856 525784 393623 401922 420164 498377 452652 437946 313265 346252 540373 354521 328272 377027 5350...
output:
185
result:
ok single line: '185'
Test #44:
score: 0
Accepted
time: 0ms
memory: 8732kb
input:
75000 15 309572 424773 306673 536382 309571 476446 309571 426866 309571 553810 309571 550279 309571 411638 309571 484195 309571 421861 309571 415509 309549 592785 309571 477174 309571 595036 309571 558902 309571 322012 309571 608663 309571 449842 309571 344104 309571 566204 309547 612039 309571 5503...
output:
67245
result:
ok single line: '67245'
Subtask #6:
score: 25
Accepted
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #45:
score: 25
Accepted
time: 17ms
memory: 9596kb
input:
75000 4000 410604329 410587776 410424452 410631988 410418203 410743533 410713313 410474264 410640116 410592458 410613972 410724413 410680849 410548408 410562034 410599280 410494222 410585156 410682785 410764170 410458899 410747514 410597013 410639866 410614975 410726571 410615337 410479269 410464829...
output:
58305
result:
ok single line: '58305'
Test #46:
score: 0
Accepted
time: 23ms
memory: 9832kb
input:
75000 8000 379545700 531059671 789043696 456086291 801707224 172489357 190682309 621309037 776674215 476995316 515935035 514774844 526482873 138591561 802873240 940651115 522037204 571918472 30455178 653354143 276671570 860679797 88077738 852805514 222921316 963894437 973362850 62228751 292554110 21...
output:
40947
result:
ok single line: '40947'
Test #47:
score: 0
Accepted
time: 15ms
memory: 9460kb
input:
75000 10000 410604329 410587776 410424452 410631988 410418203 410743533 410713313 410474264 410640116 410592458 410613972 410724413 410680849 410548408 410562034 410599280 410494222 410585156 410682785 410764170 410458899 410747514 410597013 410639866 410614975 410726571 410615337 410479269 41046482...
output:
46338
result:
ok single line: '46338'
Test #48:
score: 0
Accepted
time: 14ms
memory: 10976kb
input:
75000 1000 27768 1 27769 27769 10 27769 27769 16 18 27769 27769 27769 27769 29 27769 35 31 27769 38 44 27769 27769 49 27769 27769 55 27769 27769 27769 27769 62 67 27769 68 27769 27769 27769 77 27769 27769 84 27769 27769 27769 93 27769 27769 27769 27769 97 99 109 27769 27769 108 117 27769 27769 116 2...
output:
36723
result:
ok single line: '36723'
Test #49:
score: 0
Accepted
time: 12ms
memory: 9856kb
input:
75000 5000 36 7 37 37 37 17 37 20 17 37 19 29 25 37 29 32 37 37 37 10 15 37 37 37 37 37 37 26 37 37 8 37 7 37 37 37 14 37 37 37 37 30 26 37 37 37 36 37 45 37 45 51 46 37 49 37 5 37 37 13 37 13 37 23 37 26 28 37 37 35 29 33 41 37 40 44 37 48 48 37 37 55 37 60 59 61 63 37 3 37 11 37 19 16 37 37 26 22 ...
output:
32351
result:
ok single line: '32351'
Test #50:
score: 0
Accepted
time: 15ms
memory: 13420kb
input:
75000 1200 500000000 499925000 499925007 499925009 499925023 499925021 499925030 499925035 499925051 499925030 499925061 499925041 499925074 499925057 499925089 499925054 499925093 499925115 499925127 499925076 499925101 499925147 499925069 499925148 499925134 499925102 499925146 499925086 499925215...
output:
16070
result:
ok single line: '16070'
Test #51:
score: 0
Accepted
time: 13ms
memory: 10696kb
input:
75000 14000 309572 602912 417694 394881 603413 426950 616862 496170 346258 433524 348128 475574 435275 550668 552531 316531 363019 552916 414467 393731 602614 528639 432412 348579 471038 616330 522504 487658 487727 310254 577545 515066 603594 376094 600374 587862 510788 615407 464887 564789 429786 5...
output:
20086
result:
ok single line: '20086'
Test #52:
score: 0
Accepted
time: 9ms
memory: 9188kb
input:
75000 15000 309572 583605 339032 436735 584660 458200 599881 345990 570078 335548 346822 473269 319252 603535 315132 538589 366468 449399 463676 377082 508484 387248 421858 567519 441470 400936 427159 604164 527610 445979 390790 320068 410439 437565 447230 375954 603509 427967 429687 571758 453942 4...
output:
16538
result:
ok single line: '16538'
Test #53:
score: 0
Accepted
time: 11ms
memory: 14136kb
input:
75000 600 309572 529870 557492 564063 362113 324305 548684 451221 468647 327878 518631 548800 536400 425430 449008 348893 347681 383514 598648 378203 598879 402350 322798 606569 334693 390503 376275 554518 553311 574634 365498 248891 584274 598341 575404 607077 560953 368481 446437 504180 389472 384...
output:
1380
result:
ok single line: '1380'
Test #54:
score: 0
Accepted
time: 19ms
memory: 15152kb
input:
75000 700 309572 234309 442821 463956 503457 452757 557145 418366 546180 381349 613072 559052 575320 432042 529871 328840 435200 320971 538947 439956 517625 588549 552098 572006 521441 412398 361420 589239 385051 556349 486879 440320 588496 310555 612019 490124 453739 550020 616233 398090 329540 610...
output:
3224
result:
ok single line: '3224'
Test #55:
score: 0
Accepted
time: 10ms
memory: 13208kb
input:
75000 10000 309572 252722 352371 571614 549493 388625 451948 332478 606681 479424 421549 512124 330097 470581 501490 470104 480248 411693 502138 485187 617747 371252 551423 536614 323178 462491 445323 376483 451842 426299 404198 463899 432917 446996 416368 363265 526048 576059 403486 513584 436338 5...
output:
16564
result:
ok single line: '16564'
Subtask #7:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #56:
score: 20
Accepted
time: 377ms
memory: 55972kb
input:
2000000 1900 519086302 517948716 518115989 517881411 524464625 520838786 519785023 516500863 515614869 519526649 521886287 516511091 513888240 519647430 514370525 515779711 517648274 514574872 521322115 520709288 523573783 522256488 517673655 519326615 520980129 515991407 521393663 516554064 5204590...
output:
1980941
result:
ok single line: '1980941'
Test #57:
score: 0
Accepted
time: 371ms
memory: 57968kb
input:
2000000 1750 452021077 169849629 742646002 230893919 184391714 744112808 159695708 500802742 781813673 369083388 591529296 636452986 780631463 458368174 498271361 784180846 581655101 162648670 84989275 694850515 893757941 61708136 669639598 660789026 211003200 76852854 403840293 917750802 178037470 ...
output:
1979763
result:
ok single line: '1979763'
Test #58:
score: 0
Accepted
time: 382ms
memory: 52192kb
input:
2000000 1800 538338673 310440828 397156250 259105028 775310181 34004777 127831162 901850811 581178587 780445120 615682748 547747734 841487185 73067998 805218735 573123428 821003431 113795160 894398785 289860694 478004956 205476175 531390224 923559460 243733535 536037729 120522904 352919860 708251280...
output:
1983688
result:
ok single line: '1983688'
Test #59:
score: 0
Accepted
time: 391ms
memory: 92952kb
input:
2000000 4 817942 7 817943 817943 817943 17 817943 20 17 817943 19 29 25 817943 29 32 817943 37 817943 42 47 817943 817943 817943 817943 817943 817943 58 817943 817943 817943 68 817943 67 817943 817943 817943 74 817943 817943 817943 817943 90 86 817943 817943 817943 96 817943 105 817943 105 111 106 8...
output:
1380233
result:
ok single line: '1380233'
Test #60:
score: 0
Accepted
time: 319ms
memory: 67916kb
input:
2000000 15000 172 7 173 173 173 17 173 20 17 173 19 29 25 173 29 32 173 37 173 42 47 173 173 173 173 173 173 58 173 173 173 68 173 67 173 173 173 74 173 173 173 173 90 86 173 173 173 96 173 105 173 105 111 106 173 109 173 117 173 173 125 173 125 173 135 173 138 140 173 173 147 141 145 153 173 152 15...
output:
1211738
result:
ok single line: '1211738'
Test #61:
score: 0
Accepted
time: 323ms
memory: 43296kb
input:
2000000 5600 8289203 10286351 9263432 13584739 11810581 14338980 13346839 15964974 12590737 13182207 11610728 16306410 12023943 10008901 15944611 8402989 9190252 11779481 15095644 14190285 13973635 11753863 9741655 15901700 13162997 8440241 9048170 11233919 9825986 12399133 14726665 11857620 1439628...
output:
868644
result:
ok single line: '868644'
Test #62:
score: 0
Accepted
time: 336ms
memory: 72240kb
input:
2000000 7999 8289203 11209870 8372908 15262694 12920351 15855352 12542900 12657793 11231404 13386371 15891470 14090189 12217475 8516140 16031192 14125618 16075993 15410032 15253163 9076874 15582082 11323060 9576468 12784595 13919977 12483257 10188831 10349654 13412450 15182538 11476447 14195214 9814...
output:
929400
result:
ok single line: '929400'
Test #63:
score: 0
Accepted
time: 394ms
memory: 164580kb
input:
2000000 100000 8289203 15566074 13334263 15783149 15189497 12826100 6562654 14010976 14745751 15195664 12607086 10892498 14144976 14523483 15885552 8805251 9528680 15578857 8872490 8377547 9605104 14912911 13176756 12254664 11499684 14166828 8493396 11664111 16112784 13244085 11836297 9585865 143106...
output:
346870
result:
ok single line: '346870'
Test #64:
score: 0
Accepted
time: 426ms
memory: 152416kb
input:
2000000 259999 8289203 6426563 11101211 13995111 12842288 9732448 11652093 13895098 16236952 15751777 12216651 8598059 15683405 10919636 9433668 10879540 15668347 11471751 10709748 11658022 13263061 15920918 13637167 15892055 14343866 11565697 10217884 9453697 10780455 15370574 16404263 14631395 139...
output:
505165
result:
ok single line: '505165'
Test #65:
score: 0
Accepted
time: 328ms
memory: 42184kb
input:
2000000 560000 8289203 10913845 13151991 14923514 11254033 13632870 13976238 13447362 12072561 9515152 10758042 15147058 8646148 15596251 11871210 11639203 11682829 13806747 14609932 16405423 15767415 13142453 13310257 15827920 14729855 8777470 9268067 10859745 16014502 12347155 9253836 12898124 143...
output:
820920
result:
ok single line: '820920'
Test #66:
score: 0
Accepted
time: 302ms
memory: 48060kb
input:
2000000 199999 8289203 14493340 9004541 15172448 11380858 10946861 10743732 12141106 8579768 11100588 10154547 9369891 11064806 12886836 9573846 9920690 10289420 16561158 13127201 11861241 16226207 15669069 8430847 8346050 14517774 14539126 11659230 15395114 14914776 9831734 14872690 10537160 154557...
output:
1145441
result:
ok single line: '1145441'