求大佬看看哪有问题,调了半天了,不过第五个大样例
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,m,L,V,v,d,a,p[N],ans1,ans2,l[N],r[N],lst,cnt;
struct qp{
int ls,rs;
}car[N];
int f1(int x){
int l=1,r=m,res=m+1;
while(l<=r){
int mid=l+r>>1;
if(p[mid]>=x){
res=mid;
r=mid-1;
}
else l=mid+1;
}
return res;
}
int f2(int x){
int l=1,r=m,res=0;
while(l<=r){
int mid=l+r>>1;
if(p[mid]<=x){
res=mid;
l=mid+1;
}
else r=mid-1;
}
return res;
}
bool cmp(qp a,qp b){
return a.ls==b.ls?a.rs<b.rs:a.ls<b.ls;
}
int main(){
// freopen("detect5.in","r",stdin);
// freopen("detect.out","w",stdout);
cin>>T;
while(T--){
for(int i=1;i<=n;i++) car[i].ls=car[i].rs=0;
ans1=ans2=cnt=0;
memset(l,-1,sizeof l);
memset(r,-1,sizeof r);
cin>>n>>m>>L>>V;
for(int i=1;i<=n;i++){
cin>>d>>v>>a;
if(!a){
if(v>V) l[i]=d,r[i]=L;
continue;
}
if(a>0){
if(v>V){
l[i]=d;
r[i]=L;
continue;
}
l[i]=d+(V*V-v*v)/2/a+1;
r[i]=L;
if(l[i]>r[i]) l[i]=r[i]=-1;
}
if(a<0){
if(v<=V) continue;
l[i]=d;
r[i]=d+(V*V-v*v)/2/a;
if(l[i]>r[i]) l[i]=r[i]=-1;
}
}
for(int i=1;i<=m;i++) cin>>p[i];
for(int i=1;i<=n;i++){
if(l[i]==r[i] && l[i]==-1) continue;
int nl=f1(l[i]);
int nr=f2(r[i]);
if(nl<=nr){
ans1++;
car[++cnt]={nl,nr};
}
}
lst=-1;
sort(car+1,car+1+cnt,cmp);
for(int i=1;i<=n;i++){
int nl=car[i].ls,nr=car[i].rs;
if(nl==nr && !nl) continue;
if(nl<=lst && lst<=nr) continue;
if(nl>lst) ans2++;
lst=nr;
}
cout<<ans1<<" "<<m-ans2<<endl;
}
return 0;
}
//g++ detect.cpp -O2 -std=c++14 -Wall -o detect