40求调
查看原帖
40求调
772398
wosyioq_1367楼主2024/11/23 12:16
#include<bits/stdc++.h>
using namespace std;

const int M=1e5+10;
int t,n,m,l1,v1;
int b[M];

struct car{
	double v,ex;
	int d;
}a[M];
struct segm{
	int l,r;
}c[M];

double s1(double v,double ex,int s){
	return sqrt(v*v+2*ex*s);
}
int find1(int d,double v,double ex){
	int l=1,r=m;
	if(ex>0){
		while(l<r){
			int mid=(l+r)>>1;
			if(s1(v,ex,b[mid]-d)<=v1)l=mid+1;
			else r=mid;
		}
	}else{
		while(l<r){
			int mid=(l+r+1)>>1;
			if(s1(v,ex,b[mid]-d)<=v1)r=mid-1;
			else l=mid;
			//cout<<l<<' '<<r<<endl<<endl;
		}
	}
	return l;
}
int find2(int d){
	int l=1,r=m;
	while(l<r){
		int mid=(l+r)>>1;
		if(b[mid]<d)l=mid+1;
		else r=mid;
	}
	return l;
}
bool cmp(segm a,segm b){
	if(a.r==b.r)return a.l<b.l;
	return a.r<b.r;
}

int main(){
	//freopen("detect2.in","r",stdin);
	//freopen("detect.out","w",stdout);
	cin>>t;
	while(t--){
		int ans=0,res=0,lst=0;
		
		cin>>n>>m>>l1>>v1;
		for(int i=1;i<=n;++i)
			scanf("%d%lf%lf",&a[i].d,&a[i].v,&a[i].ex);
		for(int i=1;i<=m;++i)
			scanf("%d",&b[i]);
			
		sort(b+1,b+m+1);
		for(int i=1;i<=n;++i){
			int fst=find2(a[i].d);
			if(!a[i].ex&&a[i].v<=v1||
			a[i].ex>0&&s1(a[i].v,a[i].ex,b[m]-a[i].d)<=v1||
			a[i].ex<0&&s1(a[i].v,a[i].ex,b[fst]-a[i].d)<=v1||a[i].d>b[m]){
				c[i].l=c[i].r=0;
				continue;
			}
			ans++;
			if(!a[i].ex){
				c[i].l=fst,c[i].r=m;
			}else if(a[i].ex>0){
				c[i].l=find1(a[i].d,a[i].v,a[i].ex);
				c[i].r=m;
			}else{
				c[i].r=find1(a[i].d,a[i].v,a[i].ex);
				c[i].l=fst;
			}
		}
		for(int i=1;i<=n;i++)cout<<c[i].l<<' '<<c[i].r<<endl;
		cout<<endl;
		sort(c+1,c+n+1,cmp);
		for(int i=1;i<=n;++i){
			if(lst>=c[i].l||!c[i].l)continue;
			lst=c[i].r,res++;
		}
		cout<<ans<<' '<<m-res<<endl;
	}
	return 0;
}
2024/11/23 12:16
加载中...