QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#312794 | #5264. Wyprzedzanie | tuxuanming2024 | 65 | 275ms | 16840kb | C++14 | 1.7kb | 2024-01-24 12:10:00 | 2024-01-24 12:10:00 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include "txm/debug.h"
#endif
using namespace std;
typedef long double ld;
typedef long long ll;
const int N=100005;
const ld eps=1e-8;
int n,D,d[N],x[N],nxt[N],p[N][17],s[N],ans;
ld V,v[N],t[N],pos[N];
bool iseq(ld x,ld y) {return fabs(x-y)<eps;}
ld ask(int a,ld tt)
{
// cout<<"ask "<<a<<" "<<tt<<'\n';
if(tt<t[a]) return x[a]+v[a]*tt;
int y=a;
for(int i=16;i>=0;i--)
if(p[y][i]&&(tt>t[p[y][i]]||iseq(t[p[y][i]],tt))) y=p[y][i];
tt-=t[y];
return pos[y]+v[p[y][0]]*tt-(s[y]-s[a]);
}
signed main()
{
int w,m;
scanf("%d %d %d %d",&n,&D,&w,&m),V=(ld)w/m;
for(int i=1;i<=n;i++)
{
scanf("%d %d %d %d",x+i,d+i,&w,&m);
v[i]=(ld)w/m,s[i]=s[i-1]+d[i];
}
nxt[n]=n+1,t[n]=1e15,pos[n]=x[n];
for(int i=n-1;i>=1;i--)
{
nxt[i]=i+1;
while(nxt[i]<=n&&(v[i]<v[nxt[i]]||iseq(v[i],v[nxt[i]]))) nxt[i]=nxt[nxt[i]];
if(nxt[i]>n) {t[i]=1e15,pos[i]=x[i]; continue;}
int to=nxt[i];
ld tt=(x[to]-x[i]-(s[to]-s[i]))/(v[i]-v[to]);
if(tt>t[to]||iseq(tt,t[to]))
{
for(int j=16;j>=0;j--)
{
int k=p[nxt[i]][j];
if(!k) continue;
tt=(x[k]-x[i]-(s[k]-s[i]))/(v[i]-v[k]);
if(tt>t[k]||iseq(tt,t[k])) to=k;
}
to=p[to][0];
}
p[i][0]=to;
t[i]=(x[to]-x[i]-(s[to]-s[i]))/(v[i]-v[to]);
pos[i]=x[i]+v[i]*t[i];
for(int j=1;1<<j<=n;j++) p[i][j]=p[p[i][j-1]][j-1];
}
for(int i=1;i<=n;i++)
{
ld l=0,r=1e15,mid,tt=0;
while(!iseq(l,r))
{
mid=(l+r)/2;
if(mid*V<ask(i,mid)-d[i]) tt=mid,l=mid;
else r=mid;
}
ld L=ask(i,tt)-d[i]-ask(i-1,tt);
if(i==1||L>D||iseq(L,D)) ans++;
}
printf("%d",ans);
return 0;
}
/*
3 1 10 1
2 1 5 1
8 1 4 1
10 1 2 1
*/
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 147ms
memory: 12672kb
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: 150ms
memory: 11820kb
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: 151ms
memory: 12528kb
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: 147ms
memory: 10460kb
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: 151ms
memory: 12608kb
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: 151ms
memory: 12488kb
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: 2ms
memory: 12148kb
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: 151ms
memory: 10356kb
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: 151ms
memory: 10208kb
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: 147ms
memory: 12120kb
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: 151ms
memory: 11944kb
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: 151ms
memory: 11940kb
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: 152ms
memory: 12744kb
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: 2ms
memory: 11984kb
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: 10044kb
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: 2ms
memory: 12156kb
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: 9992kb
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: 3ms
memory: 10000kb
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: 4ms
memory: 10056kb
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: 10088kb
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: 4ms
memory: 10044kb
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: 1ms
memory: 10036kb
input:
1 1000000000 520 597 1000000000 1 780 953
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 3ms
memory: 9896kb
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: 4ms
memory: 12108kb
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: 9988kb
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: 4ms
memory: 11900kb
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: 0ms
memory: 12020kb
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: 3ms
memory: 7828kb
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: 10132kb
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: 10000kb
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: 0
Wrong Answer
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #31:
score: 35
Accepted
time: 275ms
memory: 16776kb
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: -35
Wrong Answer
time: 266ms
memory: 16840kb
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:
15539
result:
wrong answer 1st lines differ - expected: '15536', found: '15539'