大样例未过,80分,求条
查看原帖
大样例未过,80分,求条
1040584
As_linzile楼主2024/11/5 16:39
#include<bits/stdc++.h>
using namespace std;
int const N=1e5+10;
struct node
{
	int pos,v,a;
}q[N];
int cmp(node x,node y)
{
	return x.pos<y.pos;
}
int dis[N];
int main()
{
	//freopen("detect.in","r",stdin);
	//freopen("detect.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,m,L,V;
		cin>>n>>m>>L>>V;
		bool flag1=0,flag2=0,flag3=0,flag4=0,flag5=0;
		for(int i=1;i<=n;i++)
		{
			cin>>q[i].pos>>q[i].v>>q[i].a;
			if(q[i].a==0) flag1=1;
			else if(q[i].a>0) flag2=1;
			else flag3=1;
		}
		for(int i=1;i<=m;i++) cin>>dis[i];
		sort(dis+1,dis+1+m);
		sort(q+1,q+1+n,cmp);
		int ans1=0,ans2=0,mppos=m;
		double dl=0;
		for(int i=1;i<=n;i++)
		{
			if(q[i].a==0)
			{
				if(q[i].pos>dis[m]) continue;
				if(q[i].v>V&&q[i].pos<=dis[m]) ans1++,flag4=1,dl=max(dl,q[i].pos*1.0);
			}
			else if(q[i].a>0)
			{
				if(q[i].pos>dis[m]) continue;
				int d=dis[m]-q[i].pos;
				double vnow=sqrt(q[i].v*q[i].v+2*q[i].a*d);
				if(vnow>V)
				{
					ans1++;
					flag5=1;
					dl=max((V*V-q[i].v*q[i].v)*1.0/(2*q[i].a)+q[i].pos*1.0,dl);
				}
			}
			else
			{
				if(q[i].pos>dis[m]||q[i].v<=V) continue;
				double d=(q[i].v*q[i].v-V*V)*1.0/(2*(-q[i].a));
				int x=int(d+q[i].pos);
				int ppos=upper_bound(dis+1,dis+1+m,x)-dis;
				if(dis[ppos-1]>=q[i].pos)
				{
					ans1++;
					if(q[i].pos>dis[mppos])
					{
						ans2++;
						mppos=ppos-1;
					}
					else
					{
						mppos=min(mppos,ppos-1);
					}
				}
			}
		}
		cout<<ans1<<" ";
		if(flag1&&(!flag2)&&(!flag3))
		{
			if(flag4) cout<<m-1<<"\n";
			else cout<<m<<"\n";
		}
		else if((!flag1)&&flag2&&(!flag3))
		{
			if(flag5) cout<<m-1<<"\n";
			else cout<<m<<"\n";
		}
		else if((!flag1)&&(!flag2)&&flag3)
		{
			cout<<m-ans2-1<<"\n";
		}
		else
		{
			//cout<<dl<<" "<<dis[mppos]<<endl;
			if(((dl-int(dl))==0?dl:int(dl)+1)<=dis[mppos]) cout<<m-ans2-1<<"\n";
			else cout<<m-ans2-2<<"\n";
		}
	}
	return 0;
}
2024/11/5 16:39
加载中...