求调
查看原帖
求调
616449
China_yinyang楼主2024/11/6 22:42
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long n,m,L,V,p[N],len,det[N],faster,sum;
struct NODE
{
	long long d,v,a,l,r,i;
}f[N];
bool cmp(NODE a,NODE b)
{
	if(a.l!=b.l)
	return a.l>b.l;
	else
	return a.r>b.r;
}
void out()
{
	for(int i=1;i<=n;i++)
	{
		printf("%lld %lld %lld %lld %lld \n",f[i].d,f[i].v,f[i].a,f[i].l,f[i].r);
	}
	cout<<"\n\n";
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		len=0,faster=0,sum=0;
		cin>>n>>m>>L>>V;
		for(int i=1;i<=n;i++)
		{
			f[i].i=i;
			cin>>f[i].d>>f[i].v>>f[i].a;
			if(f[i].a>0)
			{
				if(f[i].v>V)
				{
					f[i].l=f[i].d;
					f[i].r=f[i].l;
				}
				else
				{
					double a=ceil(((V*V-f[i].v*f[i].v)*1.0/(2*f[i].a)))-((V*V-f[i].v*f[i].v)*1.0/(2*f[i].a));
					f[i].l=f[i].d+((V*V-f[i].v*f[i].v)*1.0/(2*f[i].a));
					if(a==0)
					f[i].l+=1;
					f[i].r=L;
				}
			}
			else if(f[i].a<0)
			{
				if(f[i].v>V)
				{
					f[i].l=f[i].d;
					double a=ceil(((V*V-f[i].v*f[i].v)*1.0/(2*f[i].a)))-((V*V-f[i].v*f[i].v)*1.0/(2*f[i].a));
					f[i].r=f[i].d+((V*V-f[i].v*f[i].v)*1.0/(2*f[i].a));
					if(a==0)
					f[i].r-=1;
				}
				else
				{
					f[i].l=-1;
					f[i].r=-1;
				}
			}
			else
			{
				if(f[i].v>V)
				{
					f[i].l=f[i].d;
					f[i].r=L;
				}
				else
				{
					f[i].l=-1;
					f[i].r=-1;
				}
			}
		}
		//out();
		for(int i=1;i<=m;i++)
		{
			cin>>p[i];
		}
		for(int i=1;i<=n;i++)
		{
			if(!(lower_bound(p+1,p+1+n,f[i].l)-p<=f[i].r)||lower_bound(p+1,p+1+n,f[i].l)-p<=0)
			f[i].l=f[i].r=-1;
		}
		sort(f+1,f+1+n,cmp);
		int start=n;
		while(f[start].l==-1)
		start--;
		long long nowl,nowr,nowp;
		nowr=f[start].r;
		nowl=f[start].l;
		nowp=lower_bound(p+1,p+1+n,f[start].l)-p;
		for(int i=start-1;i>=1;i--)
		{
			//cout<<nowl<<" "<<nowr<<" "<<p[nowp]<<endl;
			nowp=lower_bound(p+1,p+1+n,f[i].l)-p;
			if(f[i].r>=nowl&&nowl<=p[nowp]&&p[nowp]<=nowr)
			{
				nowl=max(f[i].l,/*max(p[nowp],nowl)*/nowl);
				nowr=min(f[i].r,/*min(nowr,nowp)*/nowr);
			}
			else
			{
				sum++;
				nowr=f[i].r;
				nowl=f[i].l;
			}
			faster++;
		}
		//sum++;
		cout<<faster<<" "<<m-sum<<endl;
	}
	return 0;
}
2024/11/6 22:42
加载中...