80分WA9,10
查看原帖
80分WA9,10
1407819
Massif__楼主2024/11/3 15:26

CODE:

#include<bits/stdc++.h>
using namespace std;
const int INF=1e5+50;
double V,v[INF];
int T,n,m,L,sum,sum1,d[INF],a[INF],p[INF];
struct node
{
	int l,r;
};
node s[INF];
int find(double x)
{
	int l=1,r=m+1,mid=1;
	while(l<=r)
	{
		if(p[mid]>=x&&(p[mid-1]<x||p[mid-1]==0))
			return mid;
		mid=(r-l)/2+l;
		if(p[mid]>x)
			r=mid;
		else
			if(p[mid]<x)
				l=mid+1;
	}
}
bool cmp(node x,node y)
{
	return x.l!=y.l?x.l>y.l:x.r<y.r;
}
int main()
{
	double vt,u;
	int st,t;
	scanf("%d",&T);
	for(int i=1;i<=T;i++)
	{
		memset(d,0,sizeof(d));
		memset(v,0,sizeof(v));
		memset(a,0,sizeof(a));
		memset(p,0,sizeof(p));
		memset(s,0,sizeof(s));
		sum=0;
		t=1e9;
		sum1=0;
		scanf("%d%d%d%lf",&n,&m,&L,&V);
		for(int j=1;j<=n;j++)
			scanf("%d%lf%d",&d[j],&v[j],&a[j]);
		for(int j=1;j<=m;j++)
			scanf("%d",&p[j]);
		p[m+1]=1e9;
		for(int j=1;j<=n;j++)
		{
			st=find(d[j]);
			if(a[j]>=0&&d[j]<=p[m])
			{
				u=v[j]*v[j]+2*a[j]*(p[m]-d[j]);
				vt=sqrt(u);
				if(vt>V)
				{
					sum++;
					s[sum].r=m;
					if(v[j]>V)
					{
						s[sum].l=st;
					}
					else
					{
						if(v[j]==V)
						{
							s[sum].l=find(d[j]+1);
						}
						else
							if(v[j]<V)
							{
								vt=(V*V-v[j]*v[j])/(2*a[j])+d[j];
								s[sum].l=find(vt)-1;
							}
					}
				}
			}
			else
				if(a[j]<0&&d[j]<=p[m])
				{
					st=p[st];
					u=v[j]*v[j]+2*a[j]*(st-d[j]);
					vt=sqrt(u);
					if(vt>V)
					{
						sum++;
						s[sum].l=find(d[j]);
						vt=(V*V-v[j]*v[j])/(2*a[j])+d[j];
						s[sum].r=find(vt)-1;
					}
				}
		}
		sort(s+1,s+1+sum,cmp);
		for(int j=1;j<=sum;j++)
		{
			if(s[j].r<t)
			{
				sum1++;
				t=s[j].l;
			}
		}
		printf("%d %d\n",sum,m-sum1);
	}
	return 0;
}
2024/11/3 15:26
加载中...