rt,第二问对了,第一问不对
我也不知道我是怎么打出这么抽象的代码的
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
struct Car
{
int d,v,a,dl,dr;
double l,r;
bool no;
}car[100010];
bool cmp(Car x,Car y)
{
return x.dl==y.dl?x.dr>y.dr:x.dl<y.dl;
}
bool comp(Car x,Car y)
{
return x.l<y.l;
}
int p[100010];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("detect4.in","r",stdin);
//freopen("detect.out","w",stdout);
int i,j,k,n,m,T,L,V;
cin>>T;
while(T--)
{
memset(car,0,sizeof(car));
cin>>n>>m>>L>>V;
for(i=1;i<=n;i++) cin>>car[i].d>>car[i].v>>car[i].a;
for(i=1;i<=m;i++) cin>>p[i];
for(i=1;i<=n;i++)
{
if(car[i].v>V)
{
car[i].l=car[i].d;
if(car[i].a>=0) car[i].r=inf;
else car[i].r=car[i].d+(V*V*1.00-car[i].v*car[i].v*1.00)/(2.00*car[i].a);
if(car[i].l>car[i].r) car[i].no=1;
}
else
{
if(car[i].a<=0)
{
car[i].l=inf;
car[i].r=-inf;
car[i].no=1;
}
else
{
car[i].l=car[i].d+(V*V*1.00-car[i].v*car[i].v*1.00)/(2.00*car[i].a);
car[i].r=inf;
}
}
}
int sum=n;
for(i=1;i<=n;i++)
{
int l=1,r=m,mid;
while(l<=r)//car[i].dl
{
mid=(l+r)/2;
if(p[mid]>=ceil(car[i].l))
{
car[i].dl=mid;
r=mid-1;
}
else l=mid+1;
}
l=1,r=m,mid;
while(l<=r)//car[i].dr
{
mid=(l+r)/2;
if(p[mid]<=ceil(car[i].r))
{
car[i].dr=mid;
l=mid+1;
}
else r=mid-1;
}
if(car[i].dr<=car[i].dl) sum--;
}
int ans=0,j=0;
// for(i=1;i<=n;i++) cout<<car[i].l<<" "<<car[i].r<<endl;
sort(car+1,car+n+1,cmp);
int last=-1,minn=inf;
for(i=n;i>=1;i--)
{
if(minn>=car[i].dr) minn=car[i].dr;
else car[i].no=1;
}
for(i=1;i<=n;i++)
{
if(car[i].no)
{
// sum--;
continue;
}
if(last<car[i].dl)
{
ans++;
last=car[i].dr;
}
}
cout<<sum<<" "<<m-ans<<endl;
}
}