80wa#8#10,玄关QRQ求dalao
查看原帖
80wa#8#10,玄关QRQ求dalao
1429184
ljh_struct楼主2024/11/3 09:49
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10; 
struct car{
	int s;
	int end;
};	 
int tmid=0;
car cars[MAXN];
int ans;
car luogu[MAXN];
int light[MAXN];
int flag2[MAXN];
int flag[MAXN];	
int t,n,m,k;
double vmax;
int find(int x,int l,int r){
	int mid=(l+r)/2;	
	while(l<=r){
		mid=(l+r)/2;
		tmid=mid;
		if(light[mid]<=cars[x].end&&light[mid]>=cars[x].s){
			return 1;
		}
		if(light[mid]>cars[x].end){
			r=mid-1;
		}
		if(light[mid]<cars[x].s){
			l=mid+1;
		}
	}
	return 0;
}
int find2(int x,int l,int r){
	int mid=(l+r)/2;	
	while(l<=r){
		mid=(l+r)/2;
		tmid=mid;
		if(light[mid]<=luogu[x].end&&light[mid]>=luogu[x].s){
			if(mid!=m){
				if(light[mid+1]>luogu[x].end){
					return 1;
				}
				else
					l=mid+1;
			}
			else
				return 1;
		}
		if(light[mid]>luogu[x].end){
			r=mid-1;
		}
		if(light[mid]<luogu[x].s){
			l=mid+1;
		}
	}
	return 0;
}
bool cmp1(car x,car y){
	if(x.end==y.end){
		return x.s>y.s;
	}		
	return x.end<y.end;
}
int wuli(double v,double a,double vmax){
	if(a>0){
		return ceil((vmax*vmax-v*v)/(a*2));
	}
	if(a<0){
		return ((v*v-vmax*vmax)/(a*2));
	}
}
void road(int i,int first,double v,double a,double vmax,int k){
	if(a<0&&v<=vmax){
		cars[i].end=-1;
		cars[i].s=-1;
	}
	if(a<0&&v>vmax){
		cars[i].s=first;
		cars[i].end=first-wuli(v,a,vmax);
	}
	if(a>0&&v<=vmax){
		cars[i].end=k;
		cars[i].s=first+wuli(v,a,vmax);
	}
	if(a>0&&v>vmax){
		cars[i].end=k;
		cars[i].s=first;
	}
	if(a==0&&v<=vmax){
		cars[i].end=-1;
		cars[i].s=-1;
	}
	if(a==0&&v>vmax){
		cars[i].end=k;
		cars[i].s=first;
	}
	if(cars[i].end>k){
		cars[i].end=k+1;
	}
	if(cars[i].s<0){
		cars[i].s=-1;
	}
}
void chaosu(int n,int m,int k,double vmax){
	int a;
	double b,c;
	for(int i=1;i<=n;i++){
		cin>>a>>b>>c;
		road(i,a,b,c,vmax,k);
	}
	for(int i=1;i<=m;i++){
		cin>>light[i];
	}
	ans=0;
	memset(flag2,0,sizeof(flag2));
	sort(cars+1,cars+1+n,cmp1); 
	for(int i=1;i<=n;i++){
		if(find(i,1,m)==1){	
			if(flag2[i]==0){
				ans++;
				flag2[i]=1;
				luogu[ans].end=cars[i].end;
				luogu[ans].s=cars[i].s;
			}
		}
	}
	sort(luogu+1,luogu+1+ans,cmp1);
	int ans1=m,tt=0;
	int flag1=0,cnt=0,cntt=0;
	for(int i=1;i<=ans;i++){
		if(cnt<luogu[i].s){
			if(find2(i,1,m)){		
				cnt=light[tmid];
				cntt++;
			}
		}
	}
	cout<<ans<<' '<<ans1-cntt;
	cout<<endl;
}
int main(){
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>n>>m>>k>>vmax;
		chaosu(n,m,k,vmax);
	} 
}
2024/11/3 09:49
加载中...