9,10错了,球球hack
查看原帖
9,10错了,球球hack
227950
Willow_Liu楼主2024/10/29 11:35
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 20, M = 1e6 + 20;

int p[N];

struct node
{
	int d, v, a;
} car[N];

struct nod
{
	int l, r;
} w1[N], w[N]; 

bool cmp1(node x, node y)
{
	return x.d < y.d;
}

bool cmp2(nod x, nod y)
{
	if(x.l < y.l) return 1;
	return (x.r < y.r);
}

int find1(int x, int l, int r)
{
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(p[mid] >= x)
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}
	return p[l];
}

int find2(int x, int l, int r)
{
	while(l < r)
	{
		int mid = (l + r + 1) >> 1;
		if(p[mid] > x)
		{
			r = mid - 1;
		}
		else
		{
			l = mid;
		}
	}
	return p[l];
}


int main()
{
//	freopen("detect.in", "r", stdin);
//	freopen("detect.out", "w", stdout);
	int T;
	cin >> T;
	while(T -- )
	{
		int n, m, L, V, ans1 = 0, ans2 = 0, idx = 0, id = 0;
		cin >> n >> m >> L >> V;
		for (int i = 1; i <= n; i ++ )
		{
			cin >> car[i].d >> car[i].v >> car[i].a;
		}
		for (int i = 1; i <= m; i ++ )
		{
			cin >> p[i];
		}
		sort(car + 1, car + 1 + n, cmp1);
		sort(p + 1, p + 1 + m);
		for (int i = 1; i <= n; i ++ )
		{
			int now = ans1;
			if(car[i].d > p[m]) continue;
			if(car[i].a > 0)
			{
				long long sum = 2 * (long long) car[i].a * (p[m] - car[i].d);
				int vt = ceil(sqrtl(sum + car[i].v * car[i].v));
				if(vt > V) ans1 ++; 
			}
			if(car[i].a == 0)
			{
				if(car[i].v > V) ans1 ++; 
			}
			if(car[i].a < 0)
			{
				int pm = find1(car[i].d, 1, m);
				long long sum = 2 * (long long) car[i].a * (pm - car[i].d);
				if((sum + car[i].v * car[i].v) < 0ll) continue;
				int vt = ceil(sqrtl(sum + car[i].v * car[i].v));
				if(vt > V) ans1 ++; 
			}
			if(ans1 > now)
			{
				if(car[i].a > 0)
				{
					if(car[i].v > V)
					{
						w[ ++ idx].l = car[i].d;
						w[idx].r = L;
					}
					else
					{
						w[ ++ idx].l = car[i].d + floor(((double) V * V - (double)car[i].v * car[i].v) / ((double) 2 * car[i].a)) + 1;
						w[idx].r = L;
					}
				}
				if(car[i].a == 0)
				{
					w[ ++ idx].l = car[i].d;
					w[idx].r = L;
				}
				if(car[i].a < 0)
				{
					w[ ++ idx].l = car[i].d;
					w[idx].r = car[i].d + ceil(((double) car[i].v * car[i].v - (double) V * V) / ((double) 2 * car[i].a * (-1))) - 1;
				}
			}
		}
//		for (int i = 1; i <= idx; i ++ ) cout << w[i].l << " " << w[i].r << endl;
	//	sort(w + 1, w + 1 + idx, cmp2);
		for (int i = 1; i <= idx; i ++ )
		{
			while(id != 0 && w[i].l >= w1[id].l && w[i].r <= w1[id].r)
			{
				id --;
			}
			w1[ ++ id] = {w[i].l, w[i].r};
		}
//		for (int i = 1; i <= id; i ++ ) cout << w1[i].l << " " << w1[i].r << endl;
		int last = -1;
//		sort(w1 + 1, w1 + 1 + id, cmp2);
		for (int i = 1; i <= id; i ++ )
		{
			if(last != -1)
			{
				if(w1[i].l <= last && w1[i].r >= last) continue;
				else last = -1;
			}
			int pp = find2(w1[i].r, 1, m);
			last = pp;
			ans2 ++;
		}
		
		cout << ans1 << " " << m - ans2 << endl;
	}
	return 0;
}

2024/10/29 11:35
加载中...