QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313449 | #5264. Wyprzedzanie | dyj133446 | 100 ✓ | 134ms | 15032kb | C++14 | 1.3kb | 2024-01-24 19:24:20 | 2024-01-24 19:24:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,D,x[N],dd[N],ans=1;
long long sum[N];
__float128 V,v[N],k[N],b[N],d[N],T1[N],T2[N];
int zhan[N],top;
__float128 readV()
{
int x,y;
cin>>x>>y;
return (__float128)x/y;
}
__float128 calc(__float128 k1,__float128 b1,__float128 k2,__float128 b2)
{
return (b2-b1)/(k1-k2);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>D,V=readV();
for(int i=1;i<=n;i++)cin>>x[i]>>dd[i],v[i]=readV(),sum[i]=sum[i-1]+dd[i];
for(int i=1;i<=n;i++)k[i]=v[i],b[i]=x[i]-sum[i];
d[1]=1e18;
for(int i=n;i;i--)
{
while(top&&(k[zhan[top]]>=k[i]||calc(k[zhan[top]],b[zhan[top]],k[i],b[i])>=d[top]))top--;
zhan[++top]=i;
if(top!=1)d[top]=calc(k[zhan[top]],b[zhan[top]],k[zhan[top-1]],b[zhan[top-1]]);
__float128 K=V,B=b[i]-(x[i]+D);
int l=1,r=top;
while(l<=r)
{
int mid=(l+r)/2;
if(K*d[mid]+B>=k[zhan[mid]]*d[mid]+b[zhan[mid]])l=mid+1;
else r=mid-1;
}
T1[i]=calc(K,B,k[zhan[r]],b[zhan[r]]);
B=b[i]-(x[i]-dd[i]);
l=1,r=top;
while(l<=r)
{
int mid=(l+r)/2;
if(K*d[mid]+B>=k[zhan[mid]]*d[mid]+b[zhan[mid]])l=mid+1;
else r=mid-1;
}
T2[i]=calc(K,B,k[zhan[r]],b[zhan[r]]);
}
for(int i=1;i<n;i++)if(T1[i]<=T2[i+1])ans++;
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 52ms
memory: 14556kb
input:
100000 9 445 874 1653 9 34 792 2736 336 34 792 21599 862 34 792 23975 188 34 792 41891 401 34 792 62576 193 34 792 74285 567 34 792 78959 2850 34 792 85316 452 34 792 92188 217 34 792 97244 3526 34 792 106804 599 34 792 112500 1352 34 792 120610 581 34 792 123644 213 34 792 123754 16 34 792 125589 4...
output:
99905
result:
ok single line: '99905'
Test #2:
score: 0
Accepted
time: 52ms
memory: 14700kb
input:
100000 42 423 459 37434 62 373 551 55489 515 373 551 58121 1271 373 551 62626 1237 373 551 85240 1500 373 551 100367 2450 373 551 103859 766 373 551 105195 647 373 551 113654 79 373 551 116413 2078 373 551 123362 157 373 551 128320 670 373 551 130075 1030 373 551 146426 397 373 551 155828 1195 373 5...
output:
99539
result:
ok single line: '99539'
Test #3:
score: 0
Accepted
time: 53ms
memory: 14580kb
input:
100000 514 651 267 5878 637 349 559 8958 1820 349 559 19500 1747 349 559 26299 1243 349 559 27584 995 349 559 30038 128 349 559 41755 367 349 559 46773 28 349 559 57112 3790 349 559 77098 1945 349 559 79912 346 349 559 81176 1071 349 559 96565 1741 349 559 99869 1267 349 559 105062 1131 349 559 1225...
output:
94212
result:
ok single line: '94212'
Test #4:
score: 0
Accepted
time: 52ms
memory: 15032kb
input:
100000 6903 385 122 27659 90 660 238 29771 3 660 238 33082 45 660 238 36254 55 660 238 37436 36 660 238 49934 126 660 238 56662 21 660 238 64037 20 660 238 70132 223 660 238 73123 37 660 238 74391 106 660 238 87544 26 660 238 90127 179 660 238 95773 66 660 238 108314 4 660 238 111360 113 660 238 115...
output:
49159
result:
ok single line: '49159'
Test #5:
score: 0
Accepted
time: 59ms
memory: 14556kb
input:
100000 47429 212 203 11292 49 249 293 19281 41 249 293 38517 20 249 293 65772 24 249 293 73342 63 249 293 86818 112 249 293 95250 201 249 293 98973 183 249 293 132629 18 249 293 138479 87 249 293 139269 40 249 293 140399 74 249 293 141852 100 249 293 157957 20 249 293 160317 24 249 293 160534 53 249...
output:
970
result:
ok single line: '970'
Test #6:
score: 0
Accepted
time: 55ms
memory: 14704kb
input:
100000 891884 617 488 5243 119 597 691 6747 15 597 691 14373 119 597 691 17883 52 597 691 20388 113 597 691 50660 73 597 691 58923 161 597 691 63414 61 597 691 76445 157 597 691 84324 38 597 691 88647 197 597 691 97447 498 597 691 106705 34 597 691 119011 122 597 691 150042 63 597 691 164835 102 597...
output:
2
result:
ok single line: '2'
Test #7:
score: 0
Accepted
time: 0ms
memory: 13888kb
input:
1 1000000000 761 455 1000000000 1 737 595
output:
1
result:
ok single line: '1'
Subtask #2:
score: 20
Accepted
Dependency #1:
100%
Accepted
Test #8:
score: 20
Accepted
time: 51ms
memory: 14564kb
input:
100000 9 984 1 13277 1519 1 998 50255 1248 1 991 76049 794 1 979 78294 128 1 978 84461 2332 1 969 117959 2101 1 943 138836 3303 1 932 139565 418 1 932 143805 216 1 928 150460 1323 1 928 153651 105 1 924 159235 175 1 898 165846 1922 1 891 174840 2016 1 886 184405 800 1 880 200807 711 1 878 210013 174...
output:
99963
result:
ok single line: '99963'
Test #9:
score: 0
Accepted
time: 53ms
memory: 14724kb
input:
100000 31 997 1 1041 5 1 998 14054 1061 1 982 20888 3270 1 970 40091 1054 1 940 44674 353 1 937 45648 271 1 931 48417 659 1 926 57508 1070 1 904 63225 55 1 900 66451 1733 1 898 68665 579 1 895 70696 1548 1 894 100516 530 1 883 103117 68 1 868 108640 723 1 862 113044 310 1 857 116930 421 1 857 120527...
output:
99800
result:
ok single line: '99800'
Test #10:
score: 0
Accepted
time: 48ms
memory: 14524kb
input:
100000 822 1000 1 2968 768 1 1000 21579 31 1 999 25773 1431 1 996 27447 1036 1 982 34954 255 1 982 50345 3194 1 967 59666 469 1 960 95568 2012 1 942 116776 4462 1 938 130891 1467 1 929 135657 148 1 893 137747 2 1 880 141581 2150 1 879 160529 225 1 872 170809 1500 1 872 171997 727 1 861 182071 189 1 ...
output:
91841
result:
ok single line: '91841'
Test #11:
score: 0
Accepted
time: 55ms
memory: 14704kb
input:
100000 5379 992 1 16416 11 1 997 20030 59 1 997 31208 298 1 994 35979 19 1 986 37550 80 1 981 54939 36 1 913 58490 123 1 913 62154 34 1 909 62613 20 1 862 68902 63 1 861 74561 18 1 846 82073 36 1 842 101997 112 1 842 109319 10 1 819 127017 44 1 810 132013 108 1 809 148866 11 1 804 183313 20 1 802 19...
output:
59408
result:
ok single line: '59408'
Test #12:
score: 0
Accepted
time: 55ms
memory: 14620kb
input:
100000 38590 1000 1 9503 122 1 994 9862 113 1 984 12816 72 1 951 18952 35 1 937 46312 281 1 931 59176 99 1 930 60739 30 1 928 66948 152 1 910 69161 62 1 894 74109 22 1 886 85758 114 1 881 106054 21 1 880 120363 81 1 877 134005 21 1 865 136631 39 1 864 147254 102 1 851 154084 73 1 850 158311 3 1 816 ...
output:
3428
result:
ok single line: '3428'
Test #13:
score: 0
Accepted
time: 56ms
memory: 14568kb
input:
100000 990557 987 1 11760 171 1 995 13375 117 1 988 16115 232 1 983 48046 63 1 970 58961 121 1 940 62062 40 1 933 64806 3 1 909 92075 144 1 905 107413 27 1 902 109695 80 1 899 120050 37 1 895 140820 4 1 875 146407 7 1 874 155458 143 1 861 162536 104 1 857 171054 174 1 856 175081 69 1 841 176075 37 1...
output:
199
result:
ok single line: '199'
Test #14:
score: 0
Accepted
time: 3ms
memory: 13732kb
input:
1 1000000000 859 157 1000000000 1 583 629
output:
1
result:
ok single line: '1'
Subtask #3:
score: 35
Accepted
Test #15:
score: 35
Accepted
time: 3ms
memory: 13888kb
input:
1000 5 716 3 632 108 255 785 1891 115 699 140 2143 130 778 315 3409 155 450 486 7330 57 351 675 10955 24 959 657 13151 127 37 429 13903 115 749 82 15213 37 267 276 15906 168 971 23 17068 74 751 600 18435 207 306 662 18493 4 463 490 18882 60 381 293 22184 64 888 663 27168 89 962 190 28751 121 122 898...
output:
527
result:
ok single line: '527'
Test #16:
score: 0
Accepted
time: 3ms
memory: 14020kb
input:
1000 20 917 8 1820 78 441 641 3590 90 486 512 6487 194 536 942 7056 123 266 270 8508 87 130 622 8990 30 654 463 10808 23 741 79 10932 27 228 776 11215 111 458 864 11778 38 751 153 12021 15 321 435 12053 9 162 741 12341 120 496 802 14246 23 431 808 16027 7 508 119 18356 168 362 909 20542 68 465 53 21...
output:
416
result:
ok single line: '416'
Test #17:
score: 0
Accepted
time: 0ms
memory: 12048kb
input:
1000 941 795 2 2446 276 652 673 3067 23 907 79 4023 57 20 189 4076 10 22 364 4263 46 101 752 4508 23 680 464 4777 178 638 58 5426 15 674 162 5537 43 75 564 5882 163 753 662 8162 125 142 638 9026 35 862 797 9117 57 689 398 11859 83 584 712 13277 17 897 881 13389 36 638 525 13790 20 763 810 16538 117 ...
output:
373
result:
ok single line: '373'
Test #18:
score: 0
Accepted
time: 0ms
memory: 13844kb
input:
1000 2625 10 1 477305 370 10 7 1151540 1000 7 10 1893809 12 9 1 3502666 718 4 6 3611320 296 6 6 5699350 260 3 8 8394591 596 3 10 8668961 750 2 4 11183997 981 8 7 13008836 37 10 8 14044159 2729 2 3 14287006 121 1 3 15373289 938 8 1 15724757 1165 1 4 16641191 1541 9 6 16980331 1060 7 3 17356572 4031 8...
output:
176
result:
ok single line: '176'
Test #19:
score: 0
Accepted
time: 0ms
memory: 13860kb
input:
1000 95619 10 1 26818 358 5 2 1122928 1616 6 3 1716816 175 7 10 3119287 836 9 3 3421179 3539 5 8 3570557 357 8 3 3790272 927 3 3 4240818 1211 1 9 5172443 1049 4 9 6239353 52 9 3 6675674 1504 5 3 8167258 66 9 1 9517371 2632 4 9 10547195 527 4 5 11014094 143 3 7 11841288 402 7 4 11968651 1527 5 1 1257...
output:
178
result:
ok single line: '178'
Test #20:
score: 0
Accepted
time: 0ms
memory: 14036kb
input:
1000 688304 10 1 620285 151 4 6 1034959 76 5 6 1225719 208 3 4 1713426 1012 6 7 3854628 1429 1 7 3927030 761 9 7 4437632 651 6 7 6426941 275 4 6 7028698 581 2 8 10549176 267 8 5 11653349 431 1 1 12080963 1598 6 4 13450599 672 10 5 15247541 747 7 7 15264944 2386 8 4 18172172 403 2 4 18625291 352 2 6 ...
output:
161
result:
ok single line: '161'
Test #21:
score: 0
Accepted
time: 0ms
memory: 13872kb
input:
1000 1000000 10 1 2936901 3583 8 3 4644448 1954 4 3 5097512 417 10 9 5811378 323 2 6 6649104 220 8 7 7757879 327 4 5 8882610 1914 7 10 10770045 192 9 1 11903208 1663 1 4 12418289 272 9 4 12915573 195 2 5 14421535 356 3 5 14548681 2142 1 3 15042434 1059 4 5 15846240 2657 9 9 18290147 744 4 2 18982461...
output:
147
result:
ok single line: '147'
Test #22:
score: 0
Accepted
time: 0ms
memory: 13848kb
input:
1 1000000000 520 597 1000000000 1 780 953
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 3ms
memory: 13852kb
input:
1000 1 422 1 1095880 16014 3 841 1298884 76349 5 762 1702910 111571 5 568 1912705 25792 9 830 3745225 105212 9 728 3781023 30467 11 821 10618469 1096 13 907 11803677 82134 8 535 12637880 22279 6 391 13484141 76745 15 854 14951827 5716 10 543 15505787 232803 13 598 18572957 581420 10 457 20108441 712...
output:
933
result:
ok single line: '933'
Test #24:
score: 0
Accepted
time: 3ms
memory: 13868kb
input:
1000 27 605 2 1191466 54930 2 658 1613580 23200 3 715 1962744 24271 5 774 5027396 61091 3 416 5262460 76466 3 318 5462017 38352 5 514 5662349 13044 7 627 7902840 45266 10 879 8627486 150735 3 253 10770123 38265 14 949 12223404 97148 11 692 13090647 30038 13 712 14117271 100358 4 207 14322056 56073 2...
output:
949
result:
ok single line: '949'
Test #25:
score: 0
Accepted
time: 0ms
memory: 13800kb
input:
1000 489 576 2 438069 158776 2 680 896880 30966 4 777 2877163 246055 5 822 3774194 149311 4 629 4484416 71503 8 904 5441560 280164 5 514 5782141 63987 9 827 6312864 16095 11 889 6816587 23988 12 925 7516219 336352 2 111 7969756 288358 11 573 8515585 134018 13 588 8972225 46577 11 477 9799954 62797 1...
output:
951
result:
ok single line: '951'
Test #26:
score: 0
Accepted
time: 0ms
memory: 11872kb
input:
1000 4113 10 1 869434 77 1 10 1776850 445 1 10 2302328 2 1 10 3249965 216 7 6 3828364 595 1 10 8371011 754 1 9 8390016 62 1 9 10409005 668 1 9 10942850 179 1 9 11197527 3047 1 9 11265410 2071 1 9 11960682 152 1 8 12592083 3229 1 8 14640521 3919 1 8 17632213 194 1 8 18488270 837 1 8 19259259 147 1 8 ...
output:
613
result:
ok single line: '613'
Test #27:
score: 0
Accepted
time: 3ms
memory: 13792kb
input:
1000 95698 10 1 1066719 292 1 10 3705384 1683 1 10 3801293 1773 1 10 6188356 1084 1 10 6309758 746 1 10 6877872 1506 1 10 7597138 1022 1 10 7851504 1409 1 10 9479948 689 1 10 10160908 671 1 10 11748366 930 1 10 12647207 1559 1 10 12896307 576 1 10 13777984 965 1 10 14977389 31 1 10 15072854 63 1 9 1...
output:
508
result:
ok single line: '508'
Test #28:
score: 0
Accepted
time: 0ms
memory: 13896kb
input:
1000 164349 10 1 1843692 789 1 10 2961691 1175 1 10 4644838 916 1 10 5743333 1840 1 10 5787040 225 1 10 7878423 3245 1 10 8542061 126 1 10 8920175 201 1 10 9122458 483 1 10 10402874 1156 1 10 11254248 456 1 10 12296407 554 1 10 13627737 1025 1 10 14062934 56 1 10 15916407 138 1 10 16521950 1065 1 10...
output:
502
result:
ok single line: '502'
Test #29:
score: 0
Accepted
time: 3ms
memory: 13800kb
input:
1000 999000 3 1 2160793 1003 1 2 3160863 1071 1 2 3865062 496 1 2 6138641 470 1 2 7137768 128 1 2 8138166 1400 1 2 8457449 505 1 2 9456512 65 1 2 10456359 847 1 2 11455513 156 1 2 12172673 417 1 2 13049976 5 1 2 14049235 261 1 2 15049075 841 1 2 15373229 1208 1 2 15487309 81 1 2 16486620 313 1 2 174...
output:
155
result:
ok single line: '155'
Test #30:
score: 0
Accepted
time: 3ms
memory: 11844kb
input:
1000 2 530 1 165209 2379 652 2 587177 150 642 4 1789008 110 941 10 2951053 2429 629 11 4852075 240 865 16 5588441 119 801 15 5637541 1231 895 17 7321840 2016 576 11 8149905 92 802 17 8896679 587 811 22 8987004 6409 995 29 9203597 1755 873 27 10082558 938 122 4 10670219 330 716 24 10845051 76 444 17 ...
output:
997
result:
ok single line: '997'
Subtask #4:
score: 35
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #31:
score: 35
Accepted
time: 110ms
memory: 14484kb
input:
100000 3 1000 1 1972 308 514 200 9917 166 786 713 13938 121 485 320 35714 1953 416 655 41519 120 54 771 50457 2426 200 844 58336 2488 423 471 69551 947 571 260 81080 38 295 327 82694 1171 968 440 87921 105 16 332 98168 945 652 988 104997 372 996 111 106036 591 75 279 108266 1057 162 743 115958 831 4...
output:
15680
result:
ok single line: '15680'
Test #32:
score: 0
Accepted
time: 121ms
memory: 14732kb
input:
100000 16 992 1 12313 51 907 724 14435 194 863 289 31923 179 666 478 41253 1231 233 695 44236 2087 834 456 57558 500 385 769 67717 2565 754 550 101559 361 934 386 111778 45 493 575 138322 2701 120 964 141329 442 167 325 142331 872 123 442 171455 148 988 762 172565 48 999 778 179149 75 14 431 193615 ...
output:
15536
result:
ok single line: '15536'
Test #33:
score: 0
Accepted
time: 111ms
memory: 14532kb
input:
100000 345 982 1 5016 620 233 19 17934 1318 903 450 20679 1235 235 336 58905 1045 320 161 78329 603 54 453 84947 89 515 173 88488 837 455 690 94741 1567 79 484 96806 305 324 615 97776 157 2 476 101013 256 602 176 137199 690 681 218 141530 1479 608 961 161327 493 352 809 171595 174 110 240 180892 766...
output:
15295
result:
ok single line: '15295'
Test #34:
score: 0
Accepted
time: 112ms
memory: 14484kb
input:
100000 3741 991 1 128 62 128 578 5458 666 201 411 40863 41 458 115 46152 191 193 73 60573 176 415 235 60843 63 309 964 61767 10 782 148 65048 41 136 708 81793 31 279 142 83727 168 462 212 91094 63 1 203 112286 138 472 470 115868 81 102 124 118474 10 585 272 123383 37 444 134 132631 76 568 220 134014...
output:
15254
result:
ok single line: '15254'
Test #35:
score: 0
Accepted
time: 104ms
memory: 14552kb
input:
100000 93558 986 1 613 3 877 672 3474 44 289 797 4363 50 435 680 34651 407 524 445 55007 235 73 847 58000 52 533 188 59176 344 373 632 61509 193 405 598 62951 115 613 957 63008 40 482 610 67505 376 808 634 78185 24 868 797 91217 104 652 990 98242 18 526 436 117733 65 466 900 126105 150 517 978 12969...
output:
3563
result:
ok single line: '3563'
Test #36:
score: 0
Accepted
time: 104ms
memory: 14652kb
input:
100000 248182 990 1 6977 818 172 389 8680 88 36 898 20135 249 453 752 24783 110 359 338 30831 10 65 857 34976 119 198 927 38778 141 747 731 49485 8 440 535 57422 172 208 935 58260 60 310 742 75296 129 218 910 77760 189 453 912 81155 208 346 210 81327 7 886 26 81648 35 814 686 116143 42 547 514 11946...
output:
241
result:
ok single line: '241'
Test #37:
score: 0
Accepted
time: 2ms
memory: 11840kb
input:
1 1000000000 124 408 1000000000 1 10 142
output:
1
result:
ok single line: '1'
Test #38:
score: 0
Accepted
time: 89ms
memory: 14584kb
input:
100000 9 944 1 29863 270 1 1000 32720 4 1 998 36762 25 1 978 43009 1249 1 976 45171 266 1 966 88348 852 1 966 97078 290 1 961 106486 1032 1 953 111574 37 1 952 115830 180 1 942 126974 784 1 911 131587 1361 1 907 136185 202 1 899 138912 302 1 896 145920 2214 1 858 157636 296 1 857 165145 1706 1 855 1...
output:
61119
result:
ok single line: '61119'
Test #39:
score: 0
Accepted
time: 93ms
memory: 14832kb
input:
100000 53 978 1 2887 105 1 995 6365 453 1 988 20158 418 1 980 46449 1936 1 964 87970 1254 1 905 110888 391 1 901 111210 148 390 334 113474 94 1 886 129550 934 1 882 136345 957 1 882 141966 25 1 872 149505 895 1 854 156175 641 1 840 165651 1436 1 838 190082 1246 1 819 194476 409 1 810 198342 250 1 80...
output:
61157
result:
ok single line: '61157'
Test #40:
score: 0
Accepted
time: 98ms
memory: 14704kb
input:
100000 794 994 1 613 181 1 1000 15490 158 1 995 18992 458 1 991 36516 610 1 965 42219 1808 1 960 45432 1934 1 953 49788 1640 1 950 56477 1747 1 939 61878 593 1 936 86022 28 1 929 89371 514 1 928 95096 161 1 913 109274 410 1 913 125917 3384 1 909 147950 949 1 905 153797 1243 1 887 163642 1121 1 871 1...
output:
55601
result:
ok single line: '55601'
Test #41:
score: 0
Accepted
time: 93ms
memory: 14576kb
input:
100000 8387 1000 1 18001 45 1 959 22726 26 1 922 23901 213 1 919 26170 32 1 915 26548 49 1 883 27789 67 1 881 53342 49 1 854 53738 14 1 848 54942 37 1 846 57476 92 1 844 60225 21 1 842 67170 112 1 841 68854 63 1 836 71832 111 1 807 73909 23 1 800 104312 46 1 794 121555 48 1 784 122145 240 1 783 1241...
output:
27208
result:
ok single line: '27208'
Test #42:
score: 0
Accepted
time: 94ms
memory: 14692kb
input:
100000 29732 998 1 8054 49 1 997 13469 82 1 983 28109 49 1 981 31795 12 1 973 63618 73 1 961 93928 168 1 944 100713 19 1 943 102463 112 1 937 106794 89 1 918 112478 46 1 915 157902 163 627 70 161011 399 1 913 206079 216 1 910 215780 42 1 900 217675 22 1 881 241874 147 1 835 243226 74 1 829 251305 41...
output:
4042
result:
ok single line: '4042'
Test #43:
score: 0
Accepted
time: 90ms
memory: 14740kb
input:
100000 659392 999 1 10668 45 1 998 12468 161 1 976 13823 35 1 974 20032 13 1 972 38202 99 1 961 38534 50 1 947 69236 128 1 924 70438 91 1 917 89608 151 1 912 111318 240 1 891 112035 12 1 891 112567 93 1 886 112634 36 1 861 134910 103 1 860 137829 29 1 827 167062 43 1 823 169237 139 1 797 172899 61 1...
output:
233
result:
ok single line: '233'
Test #44:
score: 0
Accepted
time: 126ms
memory: 14572kb
input:
100000 4 986 1 15881 280 966 1 20223 1080 964 1 31551 1643 944 1 42161 1737 921 1 43787 230 918 1 59093 1984 917 1 60428 889 916 1 93020 598 916 1 108702 1905 893 1 110893 198 888 1 119688 182 885 1 142970 1158 882 1 147068 1283 864 1 157857 1072 855 1 159135 374 853 1 177536 637 845 1 182900 340 84...
output:
99450
result:
ok single line: '99450'
Test #45:
score: 0
Accepted
time: 94ms
memory: 14572kb
input:
100000 1 3 1 3 1 989 352 6 1 697 294 9 1 851 317 12 1 907 431 15 1 505 221 18 1 535 263 21 1 691 257 24 1 951 422 27 1 449 157 30 1 176 85 33 1 962 465 36 1 195 77 39 1 295 139 42 1 696 275 45 1 860 361 48 1 805 269 51 1 733 268 54 1 842 297 57 1 863 350 60 1 533 228 63 1 985 368 66 1 772 371 69 1 9...
output:
402
result:
ok single line: '402'
Test #46:
score: 0
Accepted
time: 91ms
memory: 14528kb
input:
100000 1 3 1 3 1 669 257 6 1 947 465 9 1 517 197 12 1 865 429 15 1 859 326 18 1 658 249 21 1 407 139 24 1 290 131 27 1 771 266 30 1 872 291 33 1 809 364 36 1 233 106 39 1 418 175 42 1 879 413 45 1 579 239 48 1 509 183 51 1 722 289 54 1 943 439 57 1 655 281 60 1 739 282 63 1 989 357 66 1 411 166 69 1...
output:
170
result:
ok single line: '170'
Test #47:
score: 0
Accepted
time: 76ms
memory: 14476kb
input:
100000 1 3 1 3 1 737 261 6 1 599 261 9 1 937 438 12 1 863 399 15 1 621 289 18 1 434 159 21 1 757 284 24 1 676 337 27 1 666 301 30 1 591 283 33 1 854 325 36 1 652 233 39 1 661 301 42 1 521 185 45 1 688 239 48 1 394 165 51 1 489 220 54 1 547 265 57 1 443 184 60 1 992 381 63 1 524 197 66 1 443 210 69 1...
output:
101
result:
ok single line: '101'
Test #48:
score: 0
Accepted
time: 107ms
memory: 14816kb
input:
100000 1 987 1 27625 815 669 761 39037 642 118 858 56279 2756 536 179 57911 1072 996 156 60998 766 116 381 73632 342 176 454 73853 78 158 31 96877 2075 364 819 109738 18 280 508 124700 615 988 942 134622 1580 727 102 141885 1199 920 677 156201 3115 676 751 157073 826 322 112 182169 928 922 645 18575...
output:
15518
result:
ok single line: '15518'
Test #49:
score: 0
Accepted
time: 111ms
memory: 14568kb
input:
100000 46 999 1 5355 217 668 897 9172 579 330 767 12568 1419 50 902 20672 799 276 10 26094 751 860 436 35079 87 940 540 44677 154 807 245 47931 1415 814 956 51370 103 802 560 54575 212 306 733 58939 2478 406 614 69391 201 715 304 75332 143 868 903 76183 351 451 891 82915 1522 855 906 85318 359 111 9...
output:
15703
result:
ok single line: '15703'
Test #50:
score: 0
Accepted
time: 110ms
memory: 14756kb
input:
100000 240 983 1 3348 931 199 511 7633 140 253 969 11211 1578 431 150 15948 1557 387 691 27017 670 176 582 32139 1149 582 326 44230 1066 719 321 48081 83 651 437 53282 381 940 928 97719 1180 784 818 105937 476 354 523 113505 444 487 508 127271 148 558 249 131290 3873 593 997 163447 792 572 484 16848...
output:
15458
result:
ok single line: '15458'
Test #51:
score: 0
Accepted
time: 98ms
memory: 14524kb
input:
100000 3035 979 1 773 79 110 139 36665 31 737 567 56640 101 464 430 86279 40 911 149 96408 110 770 14 103766 212 293 129 107260 97 260 2 113980 51 128 982 119221 268 192 427 180913 22 676 708 182675 48 243 915 183209 74 601 937 189606 279 691 150 202184 178 757 421 212950 103 684 462 214500 135 455 ...
output:
15473
result:
ok single line: '15473'
Test #52:
score: 0
Accepted
time: 106ms
memory: 14520kb
input:
100000 79134 982 1 829 93 827 564 4513 98 843 589 5801 156 999 142 13488 71 229 47 35675 136 459 10 38409 40 345 230 72663 55 471 808 81336 150 27 579 101180 42 869 622 103452 113 351 109 108106 49 234 544 112184 69 675 267 119374 66 321 161 124751 136 748 494 133321 228 498 801 158346 241 263 557 1...
output:
4540
result:
ok single line: '4540'
Test #53:
score: 0
Accepted
time: 113ms
memory: 14552kb
input:
100000 276414 994 1 3036 14 332 988 4091 75 206 682 6342 140 486 198 19357 238 567 574 24108 116 722 189 28109 112 896 541 30129 384 821 342 30244 24 621 421 32572 47 44 584 42276 211 659 921 46513 44 518 866 54155 42 945 26 55051 57 500 814 60774 44 344 451 64458 10 674 229 75346 69 404 891 76573 2...
output:
132
result:
ok single line: '132'
Test #54:
score: 0
Accepted
time: 2ms
memory: 12000kb
input:
1 1000000000 215 173 1000000000 1 192 444
output:
1
result:
ok single line: '1'
Test #55:
score: 0
Accepted
time: 98ms
memory: 14556kb
input:
100000 1 1000 1 6432 330 1 999 14993 2787 1 988 16109 923 1 986 22109 1297 1 980 33420 207 1 959 37943 713 1 955 52203 402 1 946 62822 36 1 941 80745 159 1 930 85621 859 1 871 86969 496 1 825 117193 1539 1 818 117543 183 1 800 130187 525 1 782 134944 555 1 774 140676 67 1 770 149967 1094 1 761 15891...
output:
60317
result:
ok single line: '60317'
Test #56:
score: 0
Accepted
time: 92ms
memory: 14580kb
input:
100000 14 996 1 6038 1004 1 994 12359 1834 1 988 14186 120 1 988 15578 66 1 978 31011 1020 562 968 33884 117 1 936 37712 13 1 921 46098 1095 1 914 58144 1885 1 905 65260 2646 1 882 67667 627 1 878 78139 2383 1 875 84934 56 1 861 97529 848 1 832 102628 3168 1 826 125047 527 1 819 126444 732 1 816 140...
output:
60109
result:
ok single line: '60109'
Test #57:
score: 0
Accepted
time: 97ms
memory: 14564kb
input:
100000 312 980 1 2353 1306 1 996 28685 1801 1 995 34791 1060 1 988 41552 1687 1 980 62443 478 1 979 68160 1762 1 977 91764 1341 293 659 97458 766 1 971 103906 1282 566 822 118709 2305 1 947 123289 464 1 935 124309 160 1 933 127010 985 1 930 146363 117 1 925 154440 20 1 906 156166 673 1 897 159720 19...
output:
58067
result:
ok single line: '58067'
Test #58:
score: 0
Accepted
time: 98ms
memory: 14700kb
input:
100000 3220 999 1 17026 403 1 997 20586 13 1 989 34251 102 1 987 41178 84 1 979 56273 9 1 978 65278 16 1 967 78029 194 1 964 88005 93 1 954 92525 38 1 950 118411 1 1 949 119283 11 1 937 123908 6 1 928 141440 50 1 922 147500 70 1 920 156116 13 1 907 159753 33 1 884 180208 115 1 881 182996 145 1 871 1...
output:
44439
result:
ok single line: '44439'
Test #59:
score: 0
Accepted
time: 95ms
memory: 14472kb
input:
100000 62022 998 1 17482 19 1 1000 36001 28 1 994 55419 5 1 991 63488 337 1 989 82275 162 1 974 105278 4 1 958 108957 75 1 935 114705 137 1 925 124468 40 1 906 157598 146 1 893 166838 17 1 891 225674 34 1 878 232669 4 1 868 250037 17 1 865 253193 50 1 864 283339 210 1 852 284337 12 1 839 289486 397 ...
output:
1089
result:
ok single line: '1089'
Test #60:
score: 0
Accepted
time: 100ms
memory: 14480kb
input:
100000 295455 998 1 24447 16 1 990 34069 170 1 989 34439 279 1 968 34794 62 1 966 41039 202 1 954 49679 24 1 944 50014 47 1 941 50098 29 1 927 51632 265 1 926 55431 90 1 912 83277 115 1 905 128556 181 1 894 140393 50 1 894 140727 20 1 876 141367 189 585 106 147642 62 1 859 162448 63 1 858 172168 347...
output:
444
result:
ok single line: '444'
Test #61:
score: 0
Accepted
time: 134ms
memory: 14576kb
input:
100000 4 998 1 16041 1367 997 1 18258 1209 983 1 32981 381 982 1 37521 891 969 1 40714 603 926 1 48181 159 924 1 49507 698 915 1 51085 373 913 1 70766 952 907 1 80458 453 907 1 82863 107 895 1 90067 899 891 1 106678 157 878 1 107699 874 862 1 109472 204 852 1 121945 3032 852 1 145848 1086 804 1 1595...
output:
99510
result:
ok single line: '99510'
Test #62:
score: 0
Accepted
time: 89ms
memory: 14676kb
input:
100000 1 3 1 3 1 820 299 6 1 616 223 9 1 929 323 12 1 993 371 15 1 746 275 18 1 443 195 21 1 841 350 24 1 732 251 27 1 833 396 30 1 623 221 33 1 608 233 36 1 664 275 39 1 260 121 42 1 651 319 45 1 931 319 48 1 669 257 51 1 123 49 54 1 985 348 57 1 713 308 60 1 822 317 63 1 782 385 66 1 714 347 69 1 ...
output:
398
result:
ok single line: '398'
Test #63:
score: 0
Accepted
time: 91ms
memory: 14588kb
input:
100000 1 3 1 3 1 373 180 6 1 949 411 9 1 547 256 12 1 878 375 15 1 695 282 18 1 416 187 21 1 963 382 24 1 977 434 27 1 505 236 30 1 637 228 33 1 854 291 36 1 664 301 39 1 752 291 42 1 928 329 45 1 949 349 48 1 614 207 51 1 707 344 54 1 752 355 57 1 993 362 60 1 857 320 63 1 292 137 66 1 781 316 69 1...
output:
184
result:
ok single line: '184'
Test #64:
score: 0
Accepted
time: 88ms
memory: 14740kb
input:
100000 1 3 1 3 1 891 311 6 1 476 181 9 1 726 355 12 1 788 335 15 1 941 350 18 1 927 463 21 1 307 113 24 1 670 251 27 1 661 327 30 1 910 439 33 1 402 161 36 1 602 251 39 1 628 309 42 1 978 343 45 1 698 291 48 1 795 298 51 1 968 453 54 1 642 239 57 1 727 334 60 1 479 231 63 1 983 475 66 1 998 389 69 1...
output:
101
result:
ok single line: '101'
Test #65:
score: 0
Accepted
time: 87ms
memory: 14484kb
input:
100000 1 1000 499 3 1 991 991 6 1 988 992 9 1 1000 1000 12 1 988 990 15 1 996 1000 18 1 993 1000 21 1 982 987 24 1 992 995 27 1 988 988 30 1 991 995 33 1 1000 1000 36 1 983 997 39 1 990 996 42 1 983 1000 45 1 992 1000 48 1 993 1000 51 1 998 999 54 1 986 994 57 1 989 990 60 1 994 999 63 1 993 998 66 ...
output:
855
result:
ok single line: '855'
Test #66:
score: 0
Accepted
time: 90ms
memory: 14568kb
input:
100000 1 1000 499 3 1 992 998 6 1 991 1000 9 1 986 992 12 1 988 997 15 1 992 999 18 1 986 994 21 1 999 1000 24 1 987 996 27 1 989 995 30 1 996 999 33 1 993 998 36 1 994 998 39 1 986 989 42 1 1000 1000 45 1 985 993 48 1 982 984 51 1 986 990 54 1 990 995 57 1 988 1000 60 1 997 998 63 1 980 982 66 1 99...
output:
661
result:
ok single line: '661'
Test #67:
score: 0
Accepted
time: 80ms
memory: 14692kb
input:
100000 1 1000 499 3 1 987 990 6 1 986 996 9 1 987 991 12 1 989 998 15 1 991 996 18 1 984 987 21 1 999 1000 24 1 981 990 27 1 997 998 30 1 982 992 33 1 998 999 36 1 1000 1000 39 1 991 995 42 1 992 996 45 1 986 991 48 1 995 995 51 1 984 989 54 1 996 997 57 1 990 991 60 1 993 995 63 1 981 985 66 1 988 ...
output:
362
result:
ok single line: '362'
Test #68:
score: 0
Accepted
time: 80ms
memory: 14576kb
input:
100000 1 1000 499 3 1 998 999 6 1 986 995 9 1 999 999 12 1 981 984 15 1 997 999 18 1 986 988 21 1 987 998 24 1 982 1000 27 1 986 988 30 1 990 990 33 1 980 990 36 1 997 998 39 1 984 993 42 1 984 992 45 1 995 999 48 1 1000 1000 51 1 995 997 54 1 980 999 57 1 997 999 60 1 980 1000 63 1 995 995 66 1 985...
output:
405
result:
ok single line: '405'
Test #69:
score: 0
Accepted
time: 86ms
memory: 14524kb
input:
100000 1 1000 499 3 1 989 990 6 1 985 989 9 1 990 994 12 1 985 999 15 1 997 1000 18 1 991 999 21 1 983 1000 24 1 994 995 27 1 997 997 30 1 980 992 33 1 985 999 36 1 981 983 39 1 993 993 42 1 993 997 45 1 1000 1000 48 1 990 990 51 1 1000 1000 54 1 984 994 57 1 992 994 60 1 981 988 63 1 985 991 66 1 9...
output:
638
result:
ok single line: '638'
Test #70:
score: 0
Accepted
time: 0ms
memory: 11964kb
input:
15 1 1000 499 3 1 990 992 6 1 1 1000 9 1 1 944 142857148 1 990 997 142857151 1 1 1000 285714290 1 988 991 285714293 1 1 1000 428571432 1 999 1000 428571435 1 1 1000 571428574 1 980 981 571428577 1 1 1000 714285716 1 988 998 714285719 1 1 1000 857142858 1 986 997 857142861 1 1 1000
output:
8
result:
ok single line: '8'
Extra Test:
score: 0
Extra Test Passed