https://www.luogu.com.cn/problem/P11232
#include<bits/stdc++.h>
using namespace std;
struct node
{
int l,r;
}c[100005];
int t,n,m,L,V,s,ans,q,top,d[100005],v[100005],a[100005],p[100005];
bool flag;
bool cmp(node x,node y)
{
return x.r<y.r;
}
int main()
{
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
scanf("%d",&t);
while(t--)
{
flag=0;
s=0,ans=0;
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]);
if(a[i]<0) flag=1;
}
for(int i=1;i<=m;++i) scanf("%d",&p[i]);
sort(p+1,p+1+m);
if(flag)
{
for(int i=1;i<=n;++i)
{
if(a[i]==0)
{
if(v[i]>V&&d[i]<=p[m])
{
s++;
int l=1,r=m;
while(l<r)
{
int mid=(l+r)/2;
if(d[i]<=p[mid]) r=mid;
else l=mid+1;
}
c[s].l=r;
c[s].r=m;
}
}
if(a[i]>0)
{
int u=1.0*(V*V-v[i]*v[i]);
if(d[i]<=p[m]&&p[m]*(2*a[i])>d[i]*(2*a[i])+u)
{
s++;
int l=1,r=m;
while(l<r)
{
int mid=(l+r)/2;
if(d[i]<=p[mid]&&p[mid]*(2*a[i])>d[i]*(2*a[i])+u) r=mid;
else l=mid+1;
}
c[s].l=r;
c[s].r=m;
}
}
if(a[i]<0)
{
int l=1,r=m;
while(l<r)
{
int mid=(l+r)/2;
if(p[mid]>=d[i]) r=mid;
else l=mid+1;
}
int u=(V*V-v[i]*v[i]);
if(p[r]*(2*a[i])>d[i]*(2*a[i])+u)
{
s++;
c[s].l=r;
int ll=r,rr=m;
while(ll<rr)
{
int mid=(ll+rr+1)/2;
if(p[mid]*(2*a[i])>d[i]*(2*a[i])+u) ll=mid;
else rr=mid-1;
}
c[s].r=ll;
}
}
}
sort(c+1,c+1+s,cmp);
q=-1000000,top=0;
for(int i=1;i<=s;++i)
if(c[i].l<=q) continue;
else
{
while(top+1<=c[i].r) top++;
ans++;
q=top;
}
printf("%d %d\n",s,m-ans);
continue;
}
for(int i=1;i<=n;++i)
{
if(a[i]==0)
{
if(v[i]>V&&d[i]<=p[m]) s++;
}
if(a[i]>0)
{
int u=1.0*(V*V-v[i]*v[i]);
if(d[i]<=p[m]&&p[m]*(2*a[i])>d[i]*(2*a[i])+u) s++;
}
}
printf("%d %d\n",s,s?m-1:m);
}
return 0;
}
@zhenghaoren2024 帮我看看
