RT

不知道为什么开了两个树状数组 （甚至没离散化）

贪心没先排序而是用优先队列大幅增加常数

大常数nlogn碾过去了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=1e5+1;
const int MAXT=1e6+1;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,m,l,V;
int D[MAXN];
int T;
ll d[MAXN],v[MAXN],a[MAXN];
int tmp[MAXN];
//BIT
int c[MAXT+1][2];
int lowbit(int x){return x&-x;}
void add(int pos,int t,int r,int UP){ for(;pos<=UP;pos+=lowbit(pos)) c[pos][r]+=t;}
int qry(int pos,int r){int ret=0; for(;pos>0;pos-=lowbit(pos)) ret+=c[pos][r]; return ret;}
P Tm[MAXN];
priority_queue<P,vector<P>,greater<P> > p;
ll r(){
    ll ret=0,f=1; char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int buf[101];
void w(ll x){
    if(x==0) {putchar('0'); return;}
    int cnt=0;
    while(x){
        buf[++cnt]=x%10; x/=10;
    }
    for(int i=cnt;i>=1;--i) putchar(buf[i]+'0');
}
void solve(){
    n=r(); m=r(); l=r(); V=r();
    for(int i=1;i<=n;++i) d[i]=r(),v[i]=r(),a[i]=r();
    for(int i=1;i<=m;++i) D[i]=r(),tmp[i]=-D[i];
    for(int i=1;i<=m;++i) add(D[i],1,0,D[m]);
    sort(D+1,D+1+m);sort(tmp+1,tmp+1+m); 
    int cnt=0,cnt1=0,cnt2=0;
    for(int i=1;i<=n;++i){
        if(a[i]>0){
            ll x=-1;
            ll l=d[i],r=D[m];
            while(l<=r){
                ll mid=(l+r)>>1;
                if(2*a[i]*(mid-d[i])>V*V-v[i]*v[i]) x=mid,r=mid-1;
                else l=mid+1;
            }
            if(x!=-1)  Tm[++cnt]=P(x,D[m]),cnt1++;
        }
        if(a[i]==0){ if(v[i]>V&&d[i]<=D[m]) Tm[++cnt]=P(d[i],D[m]),cnt1++;}
        if(a[i]<0){
            if(v[i]>V){
                ll l=d[i],r=D[m]; ll x=-1;
                while(l<=r){
                    ll mid=(l+r)>>1;
                    if(-2*a[i]*(mid-d[i])<v[i]*v[i]-V*V) x=mid,l=mid+1;
                    else r=mid-1;
                }
                if(x!=-1) { if(qry(x,0)-qry(d[i]-1,0)>0) Tm[++cnt]=P(d[i],x),cnt1++;}
            }
        }
    }
    sort(Tm+1,Tm+1+cnt);
    for(int i=1;i<=cnt;++i){
        while(!p.empty()&&p.top().first<=Tm[i].first){
            P f=p.top();
            if(qry(f.first,1)-qry(f.second-1,1)==0){
                cnt2++;
                int pos=lower_bound(tmp+1,tmp+1+m,-f.first)-tmp;
                add(-tmp[pos],1,1,D[m]);
            }
            p.pop();
        }
        p.push(P(Tm[i].second,Tm[i].first));
    }
    while(!p.empty()){
        P f=p.top();
        if(qry(f.first,1)-qry(f.second-1,1)==0){
            cnt2++;
            int pos=lower_bound(tmp+1,tmp+1+m,-f.first)-tmp;
            add(-tmp[pos],1,1,D[m]);
        }
        p.pop();
    }
    for(int i=0;i<=D[m];++i) c[i][0]=c[i][1]=0;
    w(cnt1); putchar(' '); w(m-cnt2); puts("");
}
int main(){
   // freopen("detect.in","r",stdin);
   // freopen("detect.out","w",stdout);
    T=r();
    while(T--) solve();
    return 0;
}