60pts求调
查看原帖
60pts求调
1204870
sonicchen楼主2025/8/29 21:34
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define db double
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
#define pb(x) push_back(x)
const int maxn=1e5+5;
using namespace std;
int r(){
	int x=0;char c;int k=1;
	while(!isdigit(c)){
		c=getchar();if(c=='-')k=-1;	
	}
	while(isdigit(c))x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x*k;
}
vector <pii> itv;
struct Car{
	int d,v,a;
}car[maxn];
int p[maxn];
db dis(db v1,db v2,db a){
	if(v1<v2)swap(v1,v2);
	return (v1*v1-v2*v2)/fabs(a*2);
}
int main(){
	int u,v,w;
	int T,n,m,len,vm;
	T=r();
	while(T--){
		itv.clear();
		n=r(),m=r(),len=r(),vm=r();
		rep(i,1,n){
			u=r(),v=r(),w=r();
			car[i]={u,v,w};
		}
		rep(i,1,m)p[i]=r();
		int num=0;
		sort(p+1,p+1+m);
		rep(i,1,n){
			if(car[i].v<=vm&&car[i].a<=0)continue;
			if(car[i].v>vm&&car[i].a>=0){
				int pos=lower_bound(1+p,p+1+m,car[i].d)-p;
				if(pos<=m){
					num++; itv.pb(mk(m,pos));
				}
				continue;
			}
			if(car[i].v>vm){
				db tmp=dis(car[i].v,vm,car[i].a)+car[i].d;
				int pos=upper_bound(p+1,p+1+m,tmp)-p-1;
				int t=lower_bound(p+1,p+m+1,car[i].d)-p;
				if(t<=pos){
					num++;itv.pb(mk(pos,t));
				}
				continue;
			}
			db tmp=dis(car[i].v,vm,car[i].a)+car[i].d;
			int pos=lower_bound(p+1,p+m+1,tmp)-p;
			if(pos<=m){
				num++;itv.pb(mk(m,pos));
			}
		}
		sort(itv.begin(),itv.end());
		int ans=0,rt=0;
		for(auto i:itv){
			if(i.second>rt){
				ans++;rt=i.first;
			}
		}
		if(T)
		printf("%d %d\n",num,m-ans);
		else printf("%d %d",num,m-ans);

	}
}
2025/8/29 21:34
加载中...