QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#312861 | #5264. Wyprzedzanie | tuxuanming2024 | 0 | 0ms | 0kb | C++14 | 1.6kb | 2024-01-24 14:19:09 | 2024-01-24 14:19:09 |
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],ans;
ld V,v[N],t[N],pos[N];
ll s[N];
bool iseq(ld x,ld y) {return fabs(x-y)<eps;}
ld ask(int a,ld tt)
{
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]=1e19,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]=1e19,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]);
assert(t[i]<1e19);
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=1e14,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;
}
assert(iseq(tt*V,ask(i,tt)));
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;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
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:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Runtime Error
Test #15:
score: 0
Runtime Error
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:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%