讨论区hack与大样例均通过,但民间数据没过,求调
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N = 2e5 + 10;
const double esp=1e-12;
int a[N],now=1,n,T,v[N],d[N],m,L,Vt,p[N];
double V,dx;int head,tail;
int ans,ans2,dx1,dx2;
void read(int &a){
int f=1,t=0;
char ch;
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
t=t*10+ch-48;
ch=getchar();
}
a=t*f;
}
int Find(int x){
int l=0,r=m,mid=(l+r+1)>>1;
while(l<r){
if(p[mid]>x){
r=mid-1;
}else{
l=mid;
}
mid=(l+r+1)>>1;
}
return l;
}
struct car{
int from,to;
bool flag;
}c[N];
bool cmp(car a,car b){
if(a.to==b.to)return a.from<b.from;
return a.to<b.to;
}
bool check(int a,int b){
return !(a%b);
}
signed main()
{
//freopen("detect.in","r",stdin);
//freopen("detect.out","w",stdout);
read(T);
while(T--){
read(n);read(m);read(L);read(Vt);
V=Vt;
ans=ans2=now=0;
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){read(d[i]),read(v[i]),read(a[i]);}
for(int i=1;i<=m;i++)read(p[i]);
for(int i=1;i<=n;i++){
if(v[i]<=V && a[i]<=0 ){
head=tail=0;
}else if(v[i]>V && a[i]>=0){
head=d[i];tail=L;
}else if(v[i]>V){
head=d[i];
dx=(V*V-v[i]*v[i])/2/a[i];
dx1=(V*V-v[i]*v[i]);
dx2=2*a[i];
if(check(dx1,dx2))tail=d[i]+floor(dx)-1;
else tail=d[i]+floor(dx);
}else{
tail=L;
dx=(V*V-v[i]*v[i])/2/a[i];
dx1=(V*V-v[i]*v[i]);
dx2=2*a[i];
if(check(dx1,dx2))head=d[i]+ceil(dx)+1;
else head=d[i]+ceil(dx);
}//计算超速区间的位置
int f=lower_bound(p,p+m+1,head)-p;
int e=Find(tail);//第一个和最后一个捕捉到摄像头
if(f>e || e==0 && f==0)continue;
c[i].from=f;c[i].to=e;c[i].flag=true;
ans++;
}
sort(c+1,c+n+1,cmp);
int i=1;
while(i<=n){
if(c[i].flag){
ans2++;
while(now+1<=c[i].to)now++;
while(c[i].from<=now && i<=n )i++;
}else{
i++;
}
}
printf("%lld %lld\n",ans,m-ans2);
}
return 0;
}