60pts 求助
查看原帖
60pts 求助
735797
XingnoYi楼主2024/10/31 21:17
#include <iostream>
#include <cmath>
#include <algorithm>
#define big long long
using namespace std;
big T,n,m,L,V,d[100005],v[100005],a[100005],l[100005],r[100005],p[100005];
double calc(double vx,double ax)
{
	return abs(vx*vx-V*V)/(2*ax);
}
struct Node{
	big l,r;
}itr[100005];
bool cmp(Node a,Node b)
{
	return a.r < b.r;
}
big check(big k)
{
	big ll = 1,rr = m;
	while(ll <= rr)
	{
		big mid = ll+rr>>1;
		if(p[mid] >= l[k] && p[mid] <= r[k])
		{
			//printf("%lld\n",k);
			return 1;
		}
		if(p[mid] < l[k])
		{
			ll = mid+1;
		}
		if(p[mid] > r[k])
		{
			rr = mid-1;
		}
	}
	return 0;
}
big findp(big k)
{
	big rt = L+1;
	big ll = 1,rr = m;
	while(ll <= rr)
	{
		big mid = ll+rr>>1;
		if(p[mid] >= itr[k].l && p[mid] <= itr[k].r)
		{
			rt = mid;
			ll = mid+1;
		}
		if(p[mid] < itr[k].l)
		{
			ll = mid+1;
		}
		if(p[mid] > itr[k].r)
		{
			rr = mid-1;
		}
	}
	return p[rt];
}
int main()
{
	freopen("x.txt","r",stdin);
	freopen("a.txt","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		big ans = 0;
		scanf("%lld %lld %lld %lld",&n,&m,&L,&V);
		for(big i = 1;i <= n;i++)
		{
			scanf("%lld %lld %lld",d+i,v+i,a+i);
		}
		for(big i = 1;i <= n;i++)
		{
			if(v[i] <= V && a[i] <= 0)
			{
				l[i] = r[i] = L+1;
			}
			else if(v[i] > V && a[i] < 0)
			{
				double x = calc(v[i],abs(a[i]));
				l[i] = d[i];
				r[i] = min(L+1,(big)ceil(d[i]+x-1));
			}
			else if(v[i] <= V && a[i] > 0)
			{
				double x = calc(v[i],abs(a[i]));
				l[i] = min(L+1,(big)floor(d[i]+x+1));
				r[i] = L;
			}
			else if(v[i] > V && a[i] >= 0)
			{
				l[i] = d[i];
				r[i] = L;
			}
			//printf("%lld: %lld,%lld\n",i,l[i],r[i]);
		}
		big cnt = 0;
		for(big i = 1;i <= m;i++)
		{
			scanf("%lld",p+i);
		}
		for(big i = 1;i <= n;i++)
		{
			if(check(i))
			{
				itr[++cnt] = (Node){l[i],r[i]};
				//printf("%lld %lld\n",l[i],r[i]);
				ans++;
			}
		}
		printf("%lld ",ans);
		ans = 0;
		sort(itr+1,itr+cnt+1,cmp);
		for(big i = 1;i <= cnt;i++)
		{
			big tmp = findp(i);
			if(tmp != L+1)
			{
				while(itr[i].l <= tmp && tmp <= itr[i].r && i <= cnt)
				{
					i++; 
				}
				ans++;
				//printf("%lld ",tmp);
			}
		}
		printf("%lld\n",m-ans);
	}
	return 0;
}
2024/10/31 21:17
加载中...