Logo Wy Online Judge

WyOJ

Paste!

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+5;
const double eps=1e-4;
struct car{
	int sta;
	int v,ac;
};
int n,m,L,V,ans;
car a[N];
int p[N];
bool cmp(pair<double,double>x,pair<double,double>y){
	if(x.second!=y.second)	return x.second<y.second;
	else	return x.first<y.first;
}
void solve(){
	vector<pair<double,double> >seg;
	cin>>n>>m>>L>>V;
	for(int i=1;i<=n;i++)	cin>>a[i].sta>>a[i].v>>a[i].ac;
	for(int i=1;i<=n;i++){
		double l,r;
		if(a[i].ac>0){
			if(a[i].v>V){
				l=a[i].sta;
				r=L;
			}
			else{
				double tim=(V-a[i].v)*1.0/a[i].ac;
				double pos=a[i].v*tim+a[i].ac*tim*tim/2;
				if(pos>L)	l=r=-1;
				else	l=pos+a[i].sta+eps,r=L;
			}
		}
		else if(a[i].ac<0){
			if(a[i].v<=V)	l=r=-1;
			else{
				double tim=(V-a[i].v)*1.0/a[i].ac;
				double pos=a[i].v*tim+a[i].ac*tim*tim/2;
				if(pos>L)	l=r=-1;
				else	l=a[i].sta,r=pos+a[i].sta-eps;
			}
		}
		else{
			if(a[i].v>V)	l=a[i].sta,r=L;
			else	l=r=-1;
		}
		if(l==-1)	continue;
		seg.push_back({l,r});
	}
	int cur=1;
	for(int i=1;i<=m;i++)	cin>>p[i];
	sort(seg.begin(),seg.end());
	vector<pair<double,double> >ne;
	for(pair<double,double>i:seg){
		while(p[cur]<i.first)	cur++;
		if(p[cur]<=i.second)	ne.push_back(i);
	}
	cout<<ne.size()<<" ";
	p[0]=-1e9;
	cur=0;
	int cnt=0;
	sort(ne.begin(),ne.end(),cmp);
	for(pair<double,double>i:ne){
		if(i.first<=p[cur])	continue;
		while(cur+1<=m&&p[cur+1]<=i.second)	cur++;
		cnt++;
	}
	cout<<m-cnt<<"\n";
}
int main(){
	int t;
	cin>>t;
	while(t--)	solve();
	return 0;
}