有大佬吗,求助,二分好像有误
查看原帖
有大佬吗,求助,二分好像有误
1067982
Dreamer_tang楼主2024/10/29 20:01

rt

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll t;
ll n,m,L,V;
ll d[100010],v[100010],a[100010];
ll p[100010];
priority_queue< pair<ll,ll> > q;
ll check(ll x,ll y)
{
	ll s=p[x]-d[y];
	ll k=sqrt(v[y]*v[y]+2*a[y]*s);
	if(k*k!=v[y]*v[y]+2*a[y]*s)
	    k++;
	if(k>V)
	    return 1;
	else
	    return 0;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	freopen("detect2.in","r",stdin);
	freopen("detect.out","w",stdout);
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>L>>V;
		for(int i=1;i<=n;i++)
		    cin>>d[i]>>v[i]>>a[i];
		for(int i=1;i<=m;i++)
		    cin>>p[i];
		for(int i=1;i<=n;i++)
		{
			if(v[i]<=V&&a[i]<=0)
			    continue;
			if(v[i]>V&&a[i]>=0)
			{
				if(d[i]>p[m])
				    continue;
				ll k=lower_bound(p+1,p+1+m,d[i])-p;
				q.push(make_pair(m,k));
				continue;
			}
			if(v[i]>V&&a[i]<0)
			{
				if(d[i]>p[m])
				    continue;
				ll k=lower_bound(p+1,p+1+m,d[i])-p;
				ll b=sqrt(v[i]*v[i]+2*a[i]*(p[k]-d[i]));
				if(b*b!=v[i]*v[i]+2*a[i]*(p[k]-d[i]))
				    b++;
				if(b<=V)
				    continue;
				else
				{
					ll l=1,r=m;
					ll mid;
					while(l<r)
					{
						mid=l+r>>1;
						if(check(mid,i))
						    l=mid+1;
						else
						    r=mid;
					}
					q.push(make_pair(mid-1,k));
					continue;
				}
			}
			if(v[i]<V&&a[i]>0)
			{
				if(d[i]>p[m])
				    continue;
				ll b=sqrt(v[i]*v[i]+2*a[i]*(p[m]-d[i]));
				if(b*b!=v[i]*v[i]+2*a[i]*(p[m]-d[i]))
				    b++;
				if(b<=V)
				    continue;
				else
				{
					ll l=1,r=m;
					ll mid;
					while(l<r)
					{
						mid=l+r>>1;
						if(check(mid,i))
						    r=mid;
						else
						    l=mid+1;
					}
					q.push(make_pair(m,mid+1));
					continue;
				}
			}
		}
		cout<<q.size()<<" ";
	    ll h;
		ll cnt=0;
		while(!q.empty())
		{
			if(!q.empty())
			{
				h=q.top().second;
			    q.pop();
			}
			while(!q.empty()&&q.top().first>=h)
			    q.pop();
			cnt++;
		}
		cout<<m-cnt<<endl;
	}
}
2024/10/29 20:01
加载中...