rt,我是40pts,求问是不是被卡精度了,而且最后几个大样例都是正好多一个或少一个。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FOR_(i,a,b) for(int i=b;i>=a;i--)
#define fir first
#define sec second
#define pb push_back
namespace FastIO{
int buf[100]={0},p=0;
int rd(){
int x=0,f=1;char c=getchar();
while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
return x*f;
}void write(int x,char c='#'){
if(!x)putchar('0');
else{
if(x<0)putchar('-'),x*=-1;
while(x)buf[++p]=x%10,x/=10;
while(p)putchar(buf[p--]+'0');
}
if(c!='#')putchar(c);
}
};
#define rd FastIO::rd
#define write FastIO::write
typedef __int128 u128;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
const int N=1e5+10,M=1e6+10;
struct Car{int d,v,a;}cars[N];
struct Range{int l,r;}ranges[N];
struct DS{
int c[M],tot;
void clear(){memset(c,0,sizeof(c));}
#define lowbit(x) (x&(-x))
void add(int i,int k){
i++;
while(i<M)c[i]+=k,i+=lowbit(i);
}int query(int i){
i++,tot=0;
while(i)tot+=c[i],i-=lowbit(i);
return tot;
}int query(int l,int r){
if(l<=0)return query(r);
return query(r)-query(l-1);
}
#undef lowbit
}ds,ds1;
int n,m,L,V,p[N];
pii clac(int d,int v,int a){
if(a==0){
if(v>V)return {d,L};
else return {-1,-1};
}else if(a>0){
if(v>V)return {d,L};
else{
ld t=1.0*(V-v)/a;
int dd=(int)(v*t+a*t*t/2+0.9999999);
return {min(d+dd,L),L};
}
}else if(a<0){
a*=-1;
if(v<=V){
ld t=1.0*v/a;
int dd=(int)(v*t+a*t*t/2);
return {d,min(d+dd,L)};
}else{
ld t=1.0*(v-V)/a;
int dd=(int)(v*t-a*t*t/2);
return {d,min(d+dd,L)};
}
}
return {-1,-1};
}
void init(){ds.clear(),ds1.clear();}
void solve(){
init();
n=rd(),m=rd(),L=rd(),V=rd();
FOR(i,1,n){
int d=rd(),v=rd(),a=rd();
pii p=clac(d,v,a);
cars[i]={d,v,a},ranges[i]={p.fir,p.sec};
}
FOR(i,1,m)p[i]=rd(),ds.add(p[i],1);
int ans1=0,tot=0,ans2=0;
FOR(i,1,n){
int l=ranges[i].l,r=ranges[i].r;
if(ds.query(l,r))ans1++;
// printf("[%lld,%lld]\n",l,r);
}
write(ans1,' ');
FOR(i,1,n){
int l=ranges[i].l,r=ranges[i].r;
if((l<0&&r<0)||!ds.query(l,r))continue;
ranges[++tot].l=lower_bound(p+1,p+m+1,l)-p;
ranges[tot].r=upper_bound(p+1,p+m+1,r)-p-1;
// printf("[%lld,%lld]\n",ranges[tot].l,ranges[tot].r);
}
sort(ranges+1,ranges+tot+1,[&](Range r1,Range r2){return (r1.r!=r2.r)?r1.r<r2.r:r1.l<r2.l;});
// cerr<<"#\n";
// FOR(i,1,tot)printf("[%lld,%lld]\n",ranges[i].l,ranges[i].r);
FOR(i,1,tot){
int l=ranges[i].l,r=ranges[i].r;
if(ds1.query(l,r))continue;
ds1.add(r,1),ans2++;
}
write(m-ans2,'\n');
}
signed main(){
// freopen("detect4.in","r",stdin),freopen("detect.out","w",stdout);
int T=rd();
while(T--)solve();
return 0;
}