悬关求调
查看原帖
悬关求调
1063618
lxy69cmh楼主2025/1/15 23:42
#include<bits/stdc++.h>
using namespace std;
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<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x;
}
inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar((x%10)^48);
}
const int maxn=1e5+5;
struct Car{
	int d,v,a;
}car[maxn];
struct Qujian{
	int l,r;
}arr[maxn];
int T,n,m,L,V,p[maxn];
inline bool cmp(Qujian a,Qujian b){
	return b.r<a.r;
}
inline bool xiaoyu(int a,int b){
	return a<b; 
}
signed main(){
	T=read()+1;
	while(--T){
		n=read(),m=read(),L=read(),V=read();
		for(int i=1;i<=n;++i){
			car[i].d=read(),
			car[i].v=read(),
			car[i].a=read();
			arr[i].l=arr[i].r=-1;
		}
		for(int i=1;i<=m;++i){
			p[i]=read();
		}
		int ans1=0,ans2=0;
		for(int i=1;i<=n;++i){
			int d=car[i].d,v=car[i].v,a=car[i].a;
			if(d>p[m])continue;
			if(a>0){
				int s=d+ceil(1.0*(V*V-v*v)/(2*a));
				if(s>p[m])continue;
				int start=lower_bound(p+1,p+m+1,s,less<int>())-p-1;
				if(start<=m)arr[i].l=start,arr[i].r=m,++ans1;
			}else if(a<0){
				if(v<=V)continue;
				double s=d+1.0*(V*V-v*v)/(2*a);
				if(s>p[m])s=p[m];
				int start=lower_bound(p+1,p+m+1,d,less<int>())-p-1,end=lower_bound(p+1,p+m+1,s,xiaoyu)-p-1;
				if(start<=end)arr[i].l=start,arr[i].r=end,++ans1;
			}else if(a==0){
				if(v<=V)continue;
				int start=lower_bound(p+1,p+m+1,d,less<int>())-p-1;
				if(start<=m)arr[i].l=start,arr[i].r=m,++ans1;
			}
		}
		sort(arr+1,arr+1+n,cmp);
		for(int i=1;i<=m;++i){
			if(arr[i].r!=arr[i-1].r){
				++ans2;
			}
		}
		ans2=m-ans2;
		write(ans1);putchar(' ');write(ans2);putchar('\n');
	}
	return 0;
}

感谢!!!

2025/1/15 23:42
加载中...