逆天code80pts错在#1#2死活看不出来求条
查看原帖
逆天code80pts错在#1#2死活看不出来求条
715233
Dino_chx楼主2024/11/30 22:06

rt.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int T,n,m,L,V,mach[N],res[N],spr[N],tot;
struct car
{
	int spawn,v,a;
}p[N];
struct range
{
	int lq,rq;
}qs[N];
signed main()
{
	// freopen("detect4.in","r",stdin);
	// freopen("nerddino_cant_solve_q2.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		tot=0;

		scanf("%lld%lld%lld%lld",&n,&m,&L,&V);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld%lld%lld",&p[i].spawn,&p[i].v,&p[i].a);
		}
		for(int i=1;i<=m;i++)
		{
			scanf("%lld",&mach[i]);
		}
		for(int i=1;i<=n;i++)
		{
			int l=lower_bound(mach+1,mach+1+m,p[i].spawn)-mach,r=m,ans=-1;
			spr[i]=l;
			if(l>m)
			{
				res[i]=(p[i].a>=0)?m:-1;
				continue;
			}
			if(p[i].a>=0)
			{
				while(l<=r)
				{
					int mid=l+((r-l)>>1),
						dist=mach[mid]-p[i].spawn,
						curspd=p[i].v*p[i].v+2ll*p[i].a*dist;
					if(curspd<=V*V)
					{
						ans=mid;
						l=mid+1;
					}
					else
						r=mid-1;
				}
				res[i]=ans;
			}
			else
			{
				while(l<=r)
				{
					int mid=l+((r-l)>>1),
						dist=mach[mid]-p[i].spawn,
						curspd=p[i].v*p[i].v+2ll*p[i].a*dist;
					if(curspd<=0)
					{
						r=mid-1;
						continue;
					}
					if(curspd>V*V)
					{
						ans=mid;
						l=mid+1;
					}
					else
						r=mid-1;
				}
				res[i]=ans;
			}
		}
		/*
			--------------------------------question1----end-------------------------------
		*/
		int lastans1=0,lastans2=0;
		for(int i=1;i<=n;i++)
		{
			if(p[i].a>=0&&res[i]!=m)
			{
//				printf("OP the car %lld\n",i);
				lastans1++;
				qs[++tot]={res[i]+1,m};
			}
			else if(p[i].a<0&&res[i]!=-1)
			{
//				printf("OP the car %lld\n",i);
				lastans1++;
				qs[++tot]={spr[i],res[i]};
			}
		}
		sort(qs+1,qs+1+tot,[](range x,range y){return x.rq==y.rq?x.lq<y.lq:x.rq<y.rq;});
		int curp=-1;
		for(int i=1;i<=tot;i++)
		{
			if(qs[i].lq<=curp)
				continue;
			lastans2++;
			curp=qs[i].rq;
		}
		printf("%lld %lld\n",lastans1,m-lastans2);
	}
	// fclose(stdin);
	// fclose(stdout);
	return 0;
}
/*
original
1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
moved
1
5 5 15 3
15 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 14
*/
2024/11/30 22:06
加载中...