#9#10RE求调
查看原帖
#9#10RE求调
928568
zhouzihan20110620楼主2024/11/2 15:03
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps = 1e-6;
struct car
{
	long long d, v, a;
}
c[100005];
struct lr
{
	long long l, r;
}
q[100005];
long long t, n, m, l, v, p[100005], qnum, ans, lstans;
bool sortflag;
bool cmp(lr x, lr y)
{
	return x.r <= y.r;
}
int main()
{
	cin.tie(0)->ios::sync_with_stdio(false);
	cin >> t;
	p[0] = -1;
	while (t--)
	{
		cin >> n >> m >> l >> v;
		for (int i = 1;i <= n;i++)
		{
			cin >> c[i].d >> c[i].v >> c[i].a;
		}
		for (int i = 1;i <= m;i++)
		{
			cin >> p[i];
		}
		if (m)
		{
			sort(p + 1, p + m + 1);
		}
		qnum = sortflag = 0;
		for (int i = 1;i <= n;i++)
		{
			long long ll = 1e6, r = 0;
			if (c[i].a == 0)
			{
				if (c[i].v > v)
				{
					ll = c[i].d;
					r = l;
				}
			}
			else if (c[i].a > 0)
			{
				ll = max(c[i].d, c[i].d + (long long)ceil((v * v - c[i].v * c[i].v) / 2.0 / c[i].a + eps));
				r = l;
			}
			else
			{
				sortflag = 1;
				ll = c[i].d;
				r = min(l, c[i].d + (long long)floor((v * v - c[i].v * c[i].v) / 2.0 / c[i].a - eps));
			}
			if (p[upper_bound(p + 1, p + m + 1, r) - p - 1] >= ll)
			{
				q[++qnum].l = ll;
				q[qnum].r = r;
			}
		}
		if (sortflag)
		{
			sort(q + 1, q + qnum + 1, cmp);
		}
		ans = lstans = 0; 
		for (int i = 1;i <= qnum;i++)
		{
			if (p[lstans] < q[i].l)
			{
				ans++;
				lstans = upper_bound(p + 1, p + m + 1, q[i].r) - p - 1;
			}
		}
		cout << qnum << " " << m - ans << "\n";
	}
	cout << endl;
	return 0;
}

记录

2024/11/2 15:03
加载中...