QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#312861#5264. Wyprzedzanietuxuanming20240 0ms0kbC++141.6kb2024-01-24 14:19:092024-01-24 14:19:09

Judging History

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

  • [2024-01-24 14:19:09]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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%