WA 0pts求调
查看原帖
WA 0pts求调
573963
wbh20090611楼主2024/11/1 19:04

rt,

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, L, V, T, d[N], v[N], a[N], p[N], l[N], r[N], len, maxn, minn, ans, cnt;
vector <int> f[1000006];
int main()
{
	cin >> T;
	while(T--)
	{
		scanf("%d%d%d%d", &n, &m, &L, &V);
		for (int i = 1; i <= n; i++)
			scanf("%d%d%d", d + i, v + i, a + i);
		for (int i = 1; i <= m; i++)
			scanf("%d", p + i);
		for (int i = 1; i <= n; i++)
			l[i] = r[i] = L + 1;
		for (int i = 1; i <= n; i++)
		{
			if (a[i] == 0 && v[i] > V)
			{
				l[i] = d[i];
				r[i] = L + 1;
			}
			else if (a[i] > 0 && v[i] > V)
			{
				l[i] = d[i];
				r[i] = L + 1;
			}
			else if (a[i] > 0)
			{
				l[i] = min(L + 1, (int) (d[i] + floor((V * V - v[i] * v[i]) / 2.0 / a[i]) + 1));
				r[i] = L + 1; 
			}
			else if (a[i] < 0 && v[i] > V)
			{
				l[i] = d[i];
				r[i] = min(L + 1, (int) (d[i] + ceil((V * V - v[i] * v[i]) / 2.0 / a[i]) - 1));
			}
		}
		for (int i = 1; i <= n; i++)
			f[r[i]].push_back(l[i]);
		len = 0;
		for (int i = 1; i <= L + 1; i++)
			while(f[i].size())
				l[++len] = *(--f[i].end()), r[len] = i, f[i].pop_back();
		minn = -1;
		maxn = -1;
		ans = 0;
		cnt = 0;
		p[m + 1] = L + 1;
		for (int i = 1, kk; i <= n; i++)
		{
			maxn = max(maxn, r[i]); 
			if (minn < l[i])
			{
				kk = upper_bound(p + 1, p + 1 + m, r[i]) - p - 1;
				if (p[kk] < l[i])
				{
					cnt++;
					continue;
				}
				minn = p[kk];
			}
			ans++;
		}
		printf("%d %d\n", n - cnt, ans);
	}
}
2024/11/1 19:04
加载中...