10pts求条!(玄关)
查看原帖
10pts求条!(玄关)
1286553
doooge楼主2024/11/23 20:12
#include<bits/stdc++.h>
using namespace std;
const double INF=1e10;
struct ll{
	int x,speed,add,l,r;
}a[100010];
int pos[100010];
double calc(int limit,int speed,int add){
	if(add==0){
		return speed>limit?0:INF;
	}
	return (1.0*limit*limit-speed*speed)/(2.0*add);
}
bool cmp(ll x,ll y){
	if(x.l==y.l)return x.r<y.r;
	return x.l<y.l;
}
void solve(){
	int n,m,l,v,cnt=0;
	cin>>n>>m>>l>>v;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].speed>>a[i].add; 
	}
	for(int i=1;i<=m;i++){
		cin>>pos[i];
	}
	sort(pos+1,pos+m+1);
	for(int i=1;i<=n;i++){
		a[i].r=-1,a[i].l=0;
		double go=calc(v,a[i].speed,a[i].add);
		if(a[i].speed<0){
			if(a[i].add>0){
				int lpos=upper_bound(pos+1,pos+m+1,a[i].x-go)-pos;
				a[i].l=lpos;
				a[i].r=m;
			}
		}
		else{
			if(a[i].add<0){
				if(a[i].speed>v){
					int lpos=lower_bound(pos+1,pos+m+1,a[i].x+go)-pos-1;
					int lpos2=lower_bound(pos+1,pos+m+1,a[i].x)-pos;
					a[i].l=lpos2;
					a[i].r=lpos;
				}
			}
			else{
				if(a[i].add==0){
					int lpos=lower_bound(pos+1,pos+m+1,a[i].x+go)-pos;
					a[i].l=lpos;
					a[i].r=m;
					continue;
				}
				if(a[i].speed>v)go=0;
				int lpos=upper_bound(pos+1,pos+m+1,a[i].x+go)-pos;
				a[i].l=lpos;
				a[i].r=m;
			}
		}
		if(a[i].r-a[i].l>=0){
			cnt++;
		}
	}
	sort(a+1,a+n+1,cmp);
	int mn=1e9;
	for (int i=n;i>=1;i--){
		if(a[i].r<a[i].l)continue;
		if (mn<=a[i].r)a[i].l=0,a[i].r=-1;
		mn=min(mn,a[i].r);
	}
	int ans=0,last=0;
	for(int i=1;i<=n;i++){
		if(a[i].l>a[i].r)continue;
		if(last<a[i].l){
			ans++;
			last=a[i].r;
		}
	}
	cout<<cnt<<' '<<m-ans<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}
2024/11/23 20:12
加载中...