10分求调
查看原帖
10分求调
1052825
Glenn_Ren楼主2025/7/27 19:47
#include<bits/stdc++.h>
using namespace std;
int t,n,m,L,V,cnt;
int d[100005],v[100005],a[100005],ans1,p[100005];
//   s0         v0       a
struct node{
	int l,r;
}b[100005];
bool cmp(node a,node b){
	if(a.r!=b.r){
		return a.r<b.r;
	}
	else{
		return a.l<b.l;
	}
}
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline int bin(int x){
	int l=1,r=m,mid;
	int ccnt=0;
	while(l<=r){
		mid=(l+r)/2;
        if (p[mid]<x) {
            ccnt=mid;    
            l=mid+1;
        } else {
            r=mid-1;
        }
	}
	return ccnt;
}
inline void cun(int l,int r,int id){
	int x=bin(l);
	if(p[x]<l){
		x++;
	}
	int y=bin(r);
	b[id]={x,y};
}
int main(){
	//freopen("detect4.in","r",stdin);
	cin>>t;
	while(t--){
		cin>>n>>m>>L>>V;
		cnt=0;
		ans1=0;
		memset(d,0,sizeof(d));
		memset(v,0,sizeof(v));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(p,0,sizeof(p));
		for(int i=1;i<=n;i++){
			d[i]=read();v[i]=read();a[i]=read();
		}
		for(int i=1;i<=m;i++){
			p[i]=read();
		}
		sort(p+1,p+m+1);
		for(int i=1;i<=n;i++){
			if(d[i]>p[m])	continue;
			if(a[i]==0){
				if(v[i]>V){
					ans1++;
					//cout<<i<<' '<<ans1<<endl;
					cun(d[i],p[m],++cnt);
				}
				continue;
			}
			double x=V*V-v[i]*v[i];
			x/=2*a[i];
			if(a[i]>0){
				if(d[i]+x<=p[m]){
					ans1++;
					//cout<<i<<' '<<ans1<<endl;
					cun(d[i]+x,p[m],++cnt);
				}
			}else{
				double y=d[i]+x;
				//cout<<y<<' '<<bin(y)<<endl;
				if(p[bin(y)]>d[i]){
					ans1++;
					//cout<<i<<' '<<ans1<<endl;
					cun(d[i],y,++cnt);
				}
			}
		}
		sort(b+1,b+cnt+1,cmp);
		int pre=-1;
		int ans2=0;
		for(int i=1;i<=cnt;i++){
			if(b[i].l>pre){
				ans2++;
				pre=b[i].r;
			}
			//cout<<b[i].l<<' '<<b[i].r<<' '<<pre<<' '<<ans2<<endl;
		}
		printf("%d %d\n",ans1,m-ans2);
	}
	return 0;
}

2025/7/27 19:47
加载中...