#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

class car
{
public:
	int d,v,a;	
}p[100010];

int det[100010]; //探测器位置 
vector<pair<int, int>> range; //每个车的超速区间 

int main()
{
	//freopen("detect5.in","r",stdin);
	int T;
	cin >> T;
	while(T--)
	{
		range.clear();
		bool issp = true;
		int n,m,v,len;
		//cin >> n >> m >> len >> v;
		scanf("%d%d%d%d", &n, &m, &len, &v);
		for(int i = 0; i < n; i++)
		{
			//cin >> p[i].d >> p[i].v >> p[i].a;
			scanf("%d%d%d", &p[i].d, &p[i].v, &p[i].a);
			if(p[i].a != 0) issp = false;
		}
		for(int i = 0; i < m; i++)
		{
			//cin >> det[i];
			scanf("%d", &det[i]);
		}
		//a != 0
		if(!issp)
		{
			int cnt = 0;
			//遍历每辆车 
			for(int i = 0; i < n; i++)
			{ 
				if(p[i].a == 0)
				{
					//找第一个在车前的探测器 r 
					int l = -1, r = m;
					while(r-l > 1)
					{
						int mid = l+r >> 1;
						if(det[mid] < p[i].d)
						{
							l = mid;
						 } 
						else
						{
							r = mid;
						}
					}
					//防止车从来检测不到 
					if(r >= m || r < 0) continue;
					int vv = 2*p[i].a*(det[r]-p[i].d) + p[i].v * p[i].v;
					//有一个超速以后肯定会超 
					if(vv > v*v)
					{
						range.push_back({r,m-1});
						cnt++;
						//cout << i << endl;
					}
				}
				else if(p[i].a > 0)
				{
					//找第一个在车前的探测器 r 
					int l = -1, r = m;
					while(r-l > 1)
					{
						int mid = l+r >> 1;
						if(det[mid] < p[i].d)
						{
							l = mid;
						 } 
						else
						{
							r = mid;
						}
					}
					//防止车从来检测不到 
					if(r >= m || r < 0) continue;
					int st = r;
					//找第一个检测到超速的探测器 r 
					l = st-1, r = m;
					while(r-l > 1)
					{
						int mid = l+r >> 1;
						int vv = 2*p[i].a*(det[mid]-p[i].d) + p[i].v * p[i].v;
						if(vv > v*v)
						{
							r = mid;
						}
						else
						{
							l = mid;
						}
					}
					//防止从来不超速 
					if(r != m)
					{
						range.push_back({r,m-1});
						cnt++;
					}
				}
				else // a < 0 
				{
					//找第一个在车前的探测器 r 
					int l = -1, r = m;
					while(r-l > 1)
					{
						int mid = l+r >> 1;
						if(det[mid] < p[i].d)
						{
							l = mid;
						 } 
						else
						{
							r = mid;
						}
					}
					//防止车从来检测不到 
					if(r >= m || r < 0) continue;
					
					int st = r;
					//找第一个检测到不超速的 r 
					l = st-1, r = m;
					while(r-l > 1)
					{
						int mid = l+r >> 1;
						int vv = 2*p[i].a*(det[mid]-p[i].d) + p[i].v * p[i].v;
						if(vv > v*v)
						{
							l = mid;
						}
						else
						{
							r = mid;
						}
					}
					//防止从不超速 
					if(l != st-1)
					{
						range.push_back({st,l});
						cnt++;
						//cout << i << endl;
					}
				}
			 } 
			 //贪心求区间 
			sort(range.begin(), range.end());
			int must = 0;
			int last = -1;
			for(auto it = range.begin(); it != range.end(); it++)
			{
				if(it->first > last)
				{
					must++;
					last = it->second;
				}
				else
				{
					last = min(it->second, last);
				}
			}
			cout << cnt << ' ' << m-must << endl;
		}
		//a = 0
		else
		{
			sort(det, det+m);
			int cnt = 0;
			for(int i = 0; i < n; i++)
			{
				if(det[m-1] < p[i].d) continue;
				int vv = 2*p[i].a*(det[m-1]-p[i].d) + p[i].v * p[i].v;
				if(vv > v*v)
				{
					cnt++;
				}
			}
			//留最后一个就够了 
			if(cnt != 0) cout << cnt << ' ' << m-1 << endl;
			else cout << cnt << ' ' << m << endl;
		}
	} 
	
	return 0;
 } 

0 comments

No comments so far...