题目链接

提交链接

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int d[N];
int v[N];
int a[N];
int p[N];
struct node
{
	int l;
	int r;
}b[N];
int cmp(node x,node y)
{
	return x.r<y.r;
}
int t[N];
int main()
{
	int _;
	scanf("%d",&_);
	while(_--)
	{
		memset(t,0,sizeof(t));
		int n,m,l,V;
		scanf("%d %d %d %d",&n,&m,&l,&V);
		l++;
		for(int i = 1;i<=n;i++)
		{
			b[i] = {0,0};
			scanf("%d %d %d",&d[i],&v[i],&a[i]);
			d[i]++;
		}
		for(int i = 1;i<=m;i++)
		{
			scanf("%d",&p[i]);
			p[i]++;
		}
		int chao = 0;
		for(int i = 1;i<=n;i++)
		{
			if(a[i] == 0)
			{
				if(v[i]>V)
				{
					b[i] = {d[i],l};
				}
			}
			else if(a[i]<0)
			{
				int dian = (V*V-v[i]*v[i])/(2*a[i]);
				if(dian<0)
				{				
					continue;
				}
				int weiyi = d[i]+dian-(dian*2*a[i] == V*V-v[i]*v[i]);
				if(weiyi>=d[i])
				{
					b[i] = {d[i],min(weiyi,l)};
				}
			}
			else
			{
				int dian = (V*V-v[i]*v[i])/(2*a[i]);
				if(dian<0)
				{
					b[i] = {d[i],l};
					continue;
				}
				int weiyi = d[i]+dian;
				if(weiyi<=l)
				{
					b[i] = {weiyi+1,l};
				}
			}
		}
		stable_sort(b+1,b+n+1,cmp);
		int ans = 0;
		for(int i = 1;i<=n;i++)
		{
			int L = 1,R = m,cnt = 0;
			while(L<=R)
			{
				int mid = L+R>>1;
				if(p[mid]>=b[i].l&&p[mid]<=b[i].r)
				{
					cnt = 1;
					break;
				}
				else if(p[mid]>b[i].r)
				{
					R = mid-1;
				}
				else
				{
					L = mid+1; 
				}
			}
			if(cnt == 0)
			{
				b[i].r = 0;
				continue;
			}
			chao++;
		}
		for(int i = 1;i<=n;i++)
		{
			if(b[i].r == 0)
			{
				continue;
			}
			int sum = 0;
			int x = b[i].r;
			while(x)
			{
				sum+=t[x];
				x-=x&(-x);
			}
			x = b[i].l-1;
			while(x)
			{
				sum-=t[x];
				x-=x&(-x);
			}
			if(sum)
			{
				continue;
			}
			ans++;
			int L = 1,R = m,cnt = 0;
			while(L<=R)
			{
				int mid = L+R>>1;
				if(p[mid]>=b[i].l&&p[mid]<=b[i].r)
				{
					cnt = p[mid];
					L = mid+1;
				}
				else if(p[mid]>b[i].r)
				{
					R = mid-1;
				}
				else
				{
					L = mid+1; 
				}
			}
			x = cnt;
			while(x<=l)
			{
				t[x]++;
				x+=x&(-x);
			}
		}
		printf("%d %d\n",chao,m-ans);
	}
	return 0;
}