RT

80pts WA on #8 #10

没有过最后一个大样例

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,l,v,ans1,ans2,cnt,tot,ans22,ans23,ans24;
struct car{
	int d,v,a;
}s[100010];
struct quj{
	int l,r,carid;
}zk[100010];
struct qp{
	int l,r;
}tys[100010];
int p[100010];
int vis[100010];
bool cmp(qp ma,qp mi){
	if(ma.r!=mi.r)return ma.r<mi.r;
	return ma.l<mi.l;
}
bool cmp2(qp ma,qp mi){
	if(ma.l!=mi.l)return ma.l<mi.l;
	return ma.r<mi.r;
}
bool cmp5(quj ma,quj mi){
	if(ma.r!=mi.r)return ma.r<mi.r;
	return ma.l<mi.l;
}
bool cmp6(quj ma,quj mi){
	if(ma.l!=mi.l)return ma.l<mi.l;
	return ma.r<mi.r;
}
int find(int x){
	int l=1,r=m;
	while(l+1<r){
		int mid=(l+r)/2;
		if(p[mid]<=x)l=mid;
		else r=mid-1;
//		printf(" %d %d %d %d\n",x,l,r,mid);
	}
	if(p[l+1]<=x)l++;
	return l;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		ans1=0,ans2=0,cnt=0,tot=0,ans23=0,ans24=0;
		memset(vis,0,sizeof(vis));
		scanf("%lld%lld%lld%lld",&n,&m,&l,&v);
		for(int i=1;i<=n;i++){
			scanf("%lld%lld%lld",&s[i].d,&s[i].v,&s[i].a);
			if(s[i].a==0)
				if(s[i].v>v)
					zk[++cnt].l=s[i].d,zk[cnt].r=l,zk[cnt].carid=i;
			if(s[i].a>0){
				if(s[i].v>v)
					zk[++cnt].l=s[i].d,zk[cnt].r=l,zk[cnt].carid=i;
				else if(s[i].v*s[i].v+2*s[i].a*(l-s[i].d)>=v*v){
					double ls=(v*v*1.0-s[i].v*s[i].v*1.0)/(2.0*s[i].a);
					if(ls==(int)ls)ls+=1;
					zk[++cnt].l=ceil(ls+s[i].d),zk[cnt].r=l,zk[cnt].carid=i;
//					cout<<ls<<'\n';
				}
			}
			if(s[i].a<0)
				if(s[i].v>v){
					double rs=(v*v*1.0-s[i].v*s[i].v*1.0)/(2.0*s[i].a);
					if(rs==(int)rs)rs-=1;
					zk[++cnt].l=s[i].d,zk[cnt].r=min((int)floor(rs)+s[i].d,l),zk[cnt].carid=i;
				}
		}
		for(int i=1;i<=m;i++)
			scanf("%lld",&p[i]);
		p[m+1]=2147483647;
		if(n<=3000){
			sort(p+1,p+m+1);
			for(int i=1;i<=cnt;i++){
				int x=find(zk[i].l);
				if(p[x]<zk[i].l)x++;
				int y=find(zk[i].r);
//				printf(" %lld %lld %lld %lld\n",zk[i].l,zk[i].r,x,y);
				if(zk[i].l<=p[y]&&p[y]<=zk[i].r)
					ans1++,tys[++tot].l=x,tys[tot].r=y;
			}
			sort(tys+1,tys+tot+1,cmp);
			for(int i=1;i<=tot;i++){
				if(vis[i])continue;
				int ma=0,mas=0;
				for(int j=tys[i].l;j<=tys[i].r;j++){
					int sum=0;
					for(int k=i+1;k<=tot;k++)
						if(!vis[k]&&tys[k].l<=j&&j<=tys[k].r)
							sum++;
					if(sum>ma)ma=sum,mas=j;
				}
					for(int k=i;k<=tot;k++)
					if(tys[k].l<=mas&&mas<=tys[k].r)
						vis[k]=1;
				ans2++; 
			}
			printf("%lld %lld\n",ans1,m-ans2);
		}
		else{
			sort(zk+1,zk+cnt+1,cmp5);
			sort(p+1,p+m+1);
			for(int i=1;i<=cnt;i++){
				int x=p[find(zk[i].r)];
//				printf("%lld %lld %lld %lld %lld\n",i,zk[i].l,zk[i].r,zk[i].carid,x);
				if(zk[i].l<=x&&x<=zk[i].r){
					ans2++,ans1++;
					while(zk[i+1].l<=x&&x<=zk[i+1].r&&i+1<=cnt)
						i++,ans1++;
				}
			}
			sort(zk+1,zk+cnt+1,cmp6);
			for(int i=1;i<=cnt;i++){
				int x=p[find(zk[i].r)];
				if(zk[i].l<=x&&x<=zk[i].r){
					ans22++;
					while(zk[i+1].l<=x&&x<=zk[i+1].r&&i+1<=cnt)
						i++;
				}
			}
			printf("%lld %lld\n",ans1,m-min(ans2,ans22));
		}
	}
	return 0;
}