QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#291362	#2424. The short shank; Redemption	chy12321	100 ✓	124ms	42100kb	C++20	973b	2023-12-26 13:45:28	2023-12-26 13:45:29

Judging History

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

[2023-12-26 13:45:29]
评测

测评结果：100
用时：124ms
内存：42100kb

查看

[2023-12-26 13:45:28]
提交

answer

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e6 + 10;

int n, d, T, t[N], l[N], lst[N];
int top, s1[N], s2[N];
int b[N];
bool vis[N];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> d >> T; int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        if (t[i] <= T) top++, s1[top] = s2[top] = i;
        else {
            while (top && s1[top] + T - t[s1[top]] < i) {
                if (l[s2[top]] > l[i]) l[i] = l[s2[top]], lst[i] = s2[top];
                top--;
            }
            if (top) {
                if (l[s2[top]] > l[i]) l[i] = l[s2[top]], lst[i] = s2[top];
                l[i]++, vis[lst[i]] = 1, s2[top] = i;
            } else ans++, vis[i] = 1;
        }
    }
    for (int i = n; i; i--) if (!vis[i]) b[l[i]]++;
    for (int i = n; i && d > 0; i--) ans += i * min(b[i], d), d -= b[i];
    cout << n - ans;
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0

Accepted

Test #1:

score: 0

Accepted

time: 2ms

memory: 11828kb

input:

5 1 42
13 37 47 11 42

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 1ms

memory: 11856kb

input:

5 2 5
1 9 4 6 7

output:

result:

ok single line: '2'

Subtask #2:

score: 15

Accepted

Dependency #1:

100%

Accepted

Test #3:

score: 15

Accepted

time: 2ms

memory: 11844kb

input:

6 1 10
8 11 11 1 11 11

output:

result:

ok single line: '4'

Test #4:

score: 0

Accepted

time: 0ms

memory: 11776kb

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:

result:

ok single line: '348'

Test #5:

score: 0

Accepted

time: 1ms

memory: 11832kb

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:

result:

ok single line: '333'

Test #6:

score: 0

Accepted

time: 2ms

memory: 11864kb

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:

result:

ok single line: '343'

Test #7:

score: 0

Accepted

time: 1ms

memory: 11912kb

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:

result:

ok single line: '251'

Test #8:

score: 0

Accepted

time: 1ms

memory: 11884kb

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:

result:

ok single line: '333'

Test #9:

score: 0

Accepted

time: 1ms

memory: 11776kb

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:

result:

ok single line: '178'

Test #10:

score: 0

Accepted

time: 1ms

memory: 11816kb

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:

result:

ok single line: '313'

Test #11:

score: 0

Accepted

time: 0ms

memory: 11812kb

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:

result:

ok single line: '268'

Test #12:

score: 0

Accepted

time: 0ms

memory: 11764kb

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:

result:

ok single line: '188'

Test #13:

score: 0

Accepted

time: 0ms

memory: 11856kb

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:

result:

ok single line: '167'

Subtask #3:

score: 10

Accepted

Test #14:

score: 10

Accepted

time: 1ms

memory: 11856kb

input:

6 1 10
8 11 11 1 11 11

output:

result:

ok single line: '4'

Test #15:

score: 0

Accepted

time: 33ms

memory: 23304kb

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:

result:

ok single line: '499979'

Test #16:

score: 0

Accepted

time: 28ms

memory: 18344kb

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:

result:

ok single line: '499990'

Test #17:

score: 0

Accepted

time: 28ms

memory: 20320kb

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:

result:

ok single line: '470809'

Test #18:

score: 0

Accepted

time: 22ms

memory: 18940kb

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:

result:

ok single line: '484530'

Test #19:

score: 0

Accepted

time: 32ms

memory: 17364kb

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:

result:

ok single line: '272994'

Test #20:

score: 0

Accepted

time: 22ms

memory: 20936kb

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:

result:

ok single line: '799'

Test #21:

score: 0

Accepted

time: 33ms

memory: 18156kb

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:

result:

ok single line: '342417'

Subtask #4:

score: 20

Accepted

Dependency #1:

100%

Accepted

Test #22:

score: 20

Accepted

time: 0ms

memory: 9836kb

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:

result:

ok single line: '3271'

Test #23:

score: 0

Accepted

time: 2ms

memory: 11804kb

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:

result:

ok single line: '3120'

Test #24:

score: 0

Accepted

time: 2ms

memory: 11860kb

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:

result:

ok single line: '2491'

Test #25:

score: 0

Accepted

time: 0ms

memory: 11804kb

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:

result:

ok single line: '2668'

Test #26:

score: 0

Accepted

time: 1ms

memory: 11852kb

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:

result:

ok single line: '2016'

Test #27:

score: 0

Accepted

time: 0ms

memory: 11860kb

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:

result:

ok single line: '3623'

Test #28:

score: 0

Accepted

time: 1ms

memory: 11804kb

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:

result:

ok single line: '3448'

Test #29:

score: 0

Accepted

time: 1ms

memory: 11868kb

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:

result:

ok single line: '1997'

Test #30:

score: 0

Accepted

time: 1ms

memory: 11924kb

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:

result:

ok single line: '1660'

Test #31:

score: 0

Accepted

time: 0ms

memory: 11808kb

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:

result:

ok single line: '3210'

Test #32:

score: 0

Accepted

time: 0ms

memory: 11864kb

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:

result:

ok single line: '3210'

Test #33:

score: 0

Accepted

time: 1ms

memory: 11788kb

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:

result:

ok single line: '2502'

Test #34:

score: 0

Accepted

time: 1ms

memory: 11884kb

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:

result:

ok single line: '1896'

Subtask #5:

score: 10

Accepted

Test #35:

score: 10

Accepted

time: 1ms

memory: 11752kb

input:

6 1 10
8 11 11 1 11 11

output:

result:

ok single line: '4'

Test #36:

score: 0

Accepted

time: 4ms

memory: 12516kb

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:

result:

ok single line: '74734'

Test #37:

score: 0

Accepted

time: 7ms

memory: 14536kb

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:

result:

ok single line: '74831'

Test #38:

score: 0

Accepted

time: 3ms

memory: 12504kb

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:

result:

ok single line: '34154'

Test #39:

score: 0

Accepted

time: 3ms

memory: 14384kb

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:

result:

ok single line: '24540'

Test #40:

score: 0

Accepted

time: 3ms

memory: 14420kb

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:

result:

ok single line: '24211'

Test #41:

score: 0

Accepted

time: 3ms

memory: 12372kb

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:

result:

ok single line: '34039'

Test #42:

score: 0

Accepted

time: 3ms

memory: 12292kb

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:

result:

ok single line: '32924'

Test #43:

score: 0

Accepted

time: 6ms

memory: 12516kb

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:

result:

ok single line: '185'

Test #44:

score: 0

Accepted

time: 5ms

memory: 12484kb

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:

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: 6ms

memory: 12484kb

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:

result:

ok single line: '58305'

Test #46:

score: 0

Accepted

time: 6ms

memory: 12432kb

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:

result:

ok single line: '40947'

Test #47:

score: 0

Accepted

time: 3ms

memory: 12420kb

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:

result:

ok single line: '46338'

Test #48:

score: 0

Accepted

time: 5ms

memory: 12424kb

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:

result:

ok single line: '36723'

Test #49:

score: 0

Accepted

time: 5ms

memory: 12552kb

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:

result:

ok single line: '32351'

Test #50:

score: 0

Accepted

time: 0ms

memory: 12412kb

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:

result:

ok single line: '16070'

Test #51:

score: 0

Accepted

time: 6ms

memory: 12460kb

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:

result:

ok single line: '20086'

Test #52:

score: 0

Accepted

time: 0ms

memory: 12428kb

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:

result:

ok single line: '16538'

Test #53:

score: 0

Accepted

time: 5ms

memory: 12512kb

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:

result:

ok single line: '1380'

Test #54:

score: 0

Accepted

time: 3ms

memory: 14476kb

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:

result:

ok single line: '3224'

Test #55:

score: 0

Accepted

time: 0ms

memory: 12480kb

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:

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: 113ms

memory: 41608kb

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:

result:

ok single line: '1980941'

Test #57:

score: 0

Accepted

time: 115ms

memory: 40640kb

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:

result:

ok single line: '1979763'

Test #58:

score: 0

Accepted

time: 122ms

memory: 42100kb

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:

result:

ok single line: '1983688'

Test #59:

score: 0

Accepted

time: 118ms

memory: 39256kb

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:

result:

ok single line: '1380233'

Test #60:

score: 0

Accepted

time: 102ms

memory: 34960kb

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:

result:

ok single line: '1211738'

Test #61:

score: 0

Accepted

time: 124ms

memory: 27552kb

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:

result:

ok single line: '868644'

Test #62:

score: 0

Accepted

time: 114ms

memory: 33648kb

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:

result:

ok single line: '929400'

Test #63:

score: 0

Accepted

time: 114ms

memory: 35228kb

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:

result:

ok single line: '346870'

Test #64:

score: 0

Accepted

time: 121ms

memory: 36132kb

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:

result:

ok single line: '505165'

Test #65:

score: 0

Accepted

time: 116ms

memory: 32488kb

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:

result:

ok single line: '820920'

Test #66:

score: 0

Accepted

time: 102ms

memory: 33152kb

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:

result:

ok single line: '1145441'