30pts求调
查看原帖
30pts求调
1445425
zhuangzhihe楼主2025/7/31 23:55
#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct node{
	int a,v,d;
}a[N];
int p[N],led[N],t,n,m,len,v,k,h;
struct qujian{
	int l,r;
	friend bool operator<(qujian x,qujian y){
		if(x.l!=y.l) return x.l<y.l;
		return x.r>y.r;
	}
}s[N];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m>>len>>v;k=0;
		for(int i=1;i<=n;i++) cin>>a[i].d>>a[i].v>>a[i].a;
		for(int i=1;i<=m;i++) cin>>p[i];
		for(int i=1;i<=n;i++){
			if(a[i].v<=v&&a[i].a<=0) continue;
			if(a[i].a>0){
				if(a[i].v>v) h=a[i].d-1;
				else h=v*v-a[i].v*a[i].v,h/=(2*a[i].a),h+=a[i].d;
				int l=1,r=m,ans=0;
				while(l<=r){
					int mid=(l+r)>>1;
					if(p[mid]>h){
						ans=mid;
						r=mid-1;
					}else{
						l=mid+1;
					}
				}
				if(ans) s[++k].l=ans,s[k].r=m;
			}else{
				int l=1,r=m,zuo=0;
				while(l<=r){
					int mid=(l+r)>>1;
					if(p[mid]>a[i].d){
						zuo=mid;
						r=mid-1;
					}else{
						l=mid+1;
					}
				}
				if(!zuo) continue;
				l=zuo,r=m;int ans=0;
				while(l<=r){
					int mid=(l+r)>>1;
					double V=sqrt(a[i].v*a[i].v*1.0+2.0*a[i].a*(p[mid]-a[i].d));
					if(V>v){
						ans=mid;
						l=mid+1;
					}else{
						r=mid-1;
					}
				}
				if(ans>=zuo) s[++k].l=zuo,s[k].r=ans;
			}
		}
		sort(s+1,s+k+1);
		int mir=1e9;
		for(int i=k;i>=1;i--){
			if(mir<=s[i].r) led[i]=1;
			mir=min(mir,s[i].r);
		}
		int ans=0,mil=0;
		for(int i=1;i<=k;i++){
			if(led[i]){led[i]=0;continue;}
			if(mil<s[i].l){
				ans++;
				mil=s[i].r;
			}
		}
		cout<<k<<" "<<m-ans<<'\n';
	}
	return 0;
}
2025/7/31 23:55
加载中...