提交记录

#include<bits/stdc++.h>
#define cl(it) memset(it,0,sizeof it)
using namespace std;
int t,n,m,L,V,d[100005],v[100005],a[100005],p[100005],dp[100005],over;
vector<int>in[100005],out[100005];
set<int>incar,outcar;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>L>>V;
		cl(d),cl(v),cl(a),cl(p),cl(dp),over=0;
		incar.clear(),outcar.clear();
		for(int i=1;i<100005;i++)in[i].clear(),out[i].clear();
		for(int i=1;i<=n;i++)scanf("%d%d%d",&d[i],&v[i],&a[i]);
		for(int i=1;i<=m;i++)cin>>p[i];
		for(int i=1;i<=n;i++)
			if(d[i]<=p[m])
				if(a[i]==0){
					if(v[i]>V){
						in[lower_bound(p+1,p+1+m,d[i])-p].push_back(i);
						out[m+1].push_back(i);
						over++;
					}
				}else if(a[i]>0){
					if(v[i]>V){
						in[lower_bound(p+1,p+1+m,d[i])-p].push_back(i);
						out[m+1].push_back(i);
						over++;
					}else{
						long double s=((long double)1.0)*(V*V-v[i]*v[i])/2/a[i];
						if(d[i]+s-1e-8<=p[m]){
							in[lower_bound(p+1,p+1+m,d[i]+s)-p].push_back(i);
							out[m+1].push_back(i);
							over++;
						}
					}
				}else{
					if(v[i]>V){
						long double s=((long double)1.0)*(V*V-v[i]*v[i])/2/a[i];
						if(d[i]+s-1e-8>=p[lower_bound(p+1,p+1+m,d[i])-p]){
							in[lower_bound(p+1,p+1+m,d[i])-p].push_back(i);
							out[upper_bound(p+1,p+1+m,d[i]+s)-p].push_back(i);
							over++;
						};
					}
				}
		for(int i=1;i<=m;i++){
			for(int x:out[i])
				if(incar.count(x))
					outcar.insert(x);
			if(in[i].empty())dp[i]=dp[i-1];
			else{
				if(incar.empty())dp[i]=dp[i-1]+1;
				else if(outcar.empty())dp[i]=dp[i-1];
				else{
					dp[i]=dp[i-1]+1;
					incar.clear();
					outcar.clear();
				}
			}
			for(int x:in[i])incar.insert(x);
			
		}
		cout<<over<<' '<<m-dp[m]<<'\n';
	}
}