60分求条悬1关
查看原帖
60分求条悬1关
998654
__sxx楼主2025/8/30 15:12
#include<bits/stdc++.h>
#define double long double
using namespace std;
int t,n,m,nn;
double l,v,b[100005];
struct node
{
	double x,sp,spz;
}a[100005];
struct nodee
{
	int l,r;
}c[100005];
bool cmp(nodee x,nodee y)
{
	if(x.r==y.r)return x.l<y.l;
	return x.r<y.r;
}
int ef(int x)
{
	int l=0,r=m+1,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		if(x<=b[mid])r=mid;
		else l=mid;
	}
	return r;
}
int ef1(double x)
{
	int l=0,r=m+1,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		double u=b[mid];
		if(x<u)r=mid;
		else l=mid;
	}
	return r;
}
int ef2(double x)
{
	int l=0,r=m+1,mid;
	while(l+1<r)
	{
		mid=(l+r)/2;
		double u=b[mid];
		if(u<x)l=mid;
		else r=mid;
	}
	return l;
}
signed main()
{
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>l>>v;
		nn=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i].x>>a[i].sp>>a[i].spz;
		}
		for(int i=1;i<=m;i++)
		{
			cin>>b[i];
		}
		sort(b+1,b+1+m);
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i].spz==0)
			{
				if(a[i].sp<=v)
				{
					
				}
				else{
					int y=ef(a[i].x);
					if(b[m]>=a[i].x)
					{
						ans++;
						c[++nn]={y,m};
					}
						
				}
			}
			else if(a[i].spz>0)
			{ 
				if(a[i].sp>v)
				{
					int y=ef(a[i].x);
					if(b[m]>=a[i].x)ans++,c[++nn]={y,m};
				}
				else{
					double x=(double)(v*v-a[i].sp*a[i].sp)/2.00/a[i].spz;
				    double nx=(double)a[i].x+(double)x;
					int y=ef1(nx);
					if(b[y]>nx)
					{
						ans++;
						c[++nn]={y,m};
					}
				}
			}
			else
			{
				if(a[i].sp<=v)
				{
					
				}
				else
				{
					double x=(double)(v*v-a[i].sp*a[i].sp)/2.00/a[i].spz;
					double nx=a[i].x+x;
					int y=ef2(nx),yy=ef(a[i].x);
					if(a[i].x<=b[y]&&b[y]<nx)ans++,c[++nn]={yy,y};
				}
				
			}
		}
		int sum=0;
		sort(c+1,c+1+nn,cmp);
		int last=0;
		for(int i=1;i<=nn;i++)
		{
			if(c[i].l<=last&&last<=c[i].r)
			{
				
			}
			else sum++,last=c[i].r;
		}
		cout<<ans<<" "<<m-sum<<"\n";
	}
	
	return 0;
}
2025/8/30 15:12
加载中...