大样例5期望输出

2896 945
2936 853
2916 1284
2958 1946
2934 547
2951 290
2939 1729
2912 1346
2925 1382
2946 783
97336 56379
97579 4302
99107 55715
99534 5319
97519 72666
98905 44332
99278 76554
99558 73837
99589 27272
99293 66848

实际输出

2896 945
2936 853
2916 1284
2958 1946
2934 547
2951 290
2939 1729
2912 1346
2925 1382
2946 783
97336 56379
97579 4302
99107 55715
99534 5319
97519 72666
98905 44332
99278 76554
99558 73838
99589 27272
99293 66850

最后三行有锅，求条——感激不尽

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define db double 
const int maxn=2e5+10;
int n,m,tot,V,v[maxn+10],p[maxn+10],d[maxn+10],a[maxn+10];
db L;
bool bj[maxn+10],bj_[maxn+10];
struct E{
	db l,r;
	bool operator<(const E& y){
		if(y.r!=r)return y.r>r;
		return y.l<l;
	}
}e[maxn+10];
double get(double l,double r){/*[l,r]内的最近l的dis*/
	int L=1,R=m,ans=-1;
	while(L<=R){
		int mid=L+R>>1;
		if(p[mid]<l)L=mid+1;
		else if(p[mid]>r)R=mid-1;
		else {ans=mid,R=mid-1;}
	}
	if(ans==-1)return -1;
	return p[ans];
}

int CNT(){
	int cnt=0;
	for(int i=1;i<=n;++i){
		if(d[i]>p[m])continue;
		if(a[i]==0){
			if(v[i]>V)cnt++,bj_[i]=1;
		}
		else if(a[i]>0){
			if(V*V<=v[i]*v[i]+2*a[i]*(p[m]-d[i]))
				cnt++,bj_[i]=1;
		}
		else if(get(d[i],L)!=-1){
			int dt=v[i]*v[i]+2*a[i]*(get(d[i],L)-d[i]);
			if(dt>=0&&V*V<dt)cnt++,bj_[i]=1;
		}
	}
	return cnt;
}
int find(double l,double r){/*[l,r]内的最近r的编号*/
	int L=1,R=m,ans=-1;
	while(L<=R){
		int mid=L+R>>1;
		if(p[mid]<l)L=mid+1;
		else if(p[mid]>r)R=mid-1;
		else {ans=mid,L=mid+1;}
	}
	return ans;
}

signed main(){
//	freopen("detect5.in","r",stdin);
//	freopen("detect.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	int t;cin>>t;
	while(t--){
		memset(bj,0,sizeof bj);
		memset(bj_,0,sizeof bj_);
		cin>>n>>m>>L>>V;
		for(int i=1;i<=n;++i)cin>>d[i]>>v[i]>>a[i];
		for(int i=1;i<=m;++i)cin>>p[i];
		sort(p+1,p+1+m);
		cout<<CNT();
		tot=0;
		/*处理每辆车超速的区间*/
		for(int i=1;i<=n;++i){
			if(!bj_[i])continue;
			if(a[i]==0){
				if(V<v[i])e[++tot].l=d[i],e[tot].r=L;
			}
			if(a[i]>0){
				if(V<v[i])e[++tot].l=d[i],e[tot].r=L;
				else if(d[i]+1.0*(V*V-v[i]*v[i])/(2.0*a[i])<=L){
					e[++tot].l=d[i]+(double)1.00*(V*V-v[i]*v[i])/(2.00*a[i]);
					e[tot].r=L;
				}
			}
			if(a[i]<0){
				if(V<v[i]){
					e[++tot].l=d[i];e[tot].r=d[i]+(int)(V*V-v[i]*v[i])/(2*a[i]);
				}
			}
		}
		sort(e+1,e+1+tot);
	
		int ans=0;
		for(int i=1;i<=tot;++i){
			int pos=find(e[i].l,e[i].r);
			bj[pos]=1;
			while(e[i+1].l<=p[pos]&&p[pos]<=e[i+1].r&&i+1<=tot)i++;
		
		}
		for(int i=1;i<=m;++i)if(bj[i])ans++;
		cout<<" "<<m-ans<<"\n";
		
	}
	
	
	return 0;
}
/*
fc detect.out detect5.ans
*/