RJDAIMN666强者
查看原帖
RJDAIMN666强者
1088988
zzsz044楼主2024/11/26 15:43
#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
using namespace std;
struct car{
    int d,v,a;
}e[N];
struct node{
    int l,r;
}d[N];
int n,m,L,V,p[N],l,r,ll,rr,lll,rrr,mid,ans1,ans2,fnt;
int spe(int id,int pos){
    if(e[id].d>pos) return -INF;
    return 2*e[id].a*(pos-e[id].d)+e[id].v*e[id].v;
}
bool cmp(node x,node y){
    return x.r<y.r;
}
void solve(){
    cin>>n>>m>>L>>V,ans1=ans2=0; 
    for(int i=1,d,v,a;i<=n;i++){
        cin>>d>>v>>a;
        e[i]=car{d,v,a};
    }
    for(int i=1;i<=m;i++) cin>>p[i];
    for(int i=1,k;i<=n;i++){
        if(e[i].a>=0){
            l=1,r=m+1;
            while(l<r){
                mid=l+r>>1;
                if(spe(i,p[mid])>V*V) r=mid;
                else l=mid+1;
            }
            if(l!=m+1){
                d[++ans1]=node{l,m};
            }
            continue;
        }
        ll=0,rr=m;
        while(ll<rr){
            mid=ll+rr+1>>1;
            if(2ll*p[mid]*e[i].a>=2ll*e[i].d*e[i].a-e[i].v*e[i].v) ll=mid;
            else rr=mid-1;
        }
        if(!ll) continue;
        lll=1,rrr=m+1;
        while(lll<rrr){
            mid=lll+rrr>>1;
            if(p[mid]<e[i].d) lll=mid+1;
            else rrr=mid;
        }
        if(lll==m+1) continue;
        l=lll-1,r=ll;
        while(l<r){
            mid=l+r+1>>1;
            if(spe(i,p[mid])>V*V) l=mid;
            else r=mid-1;
        }
        if(l==lll-1) continue;
        d[++ans1]=node{lll,l};
    }
    cout<<ans1<<" ";r=0;
    sort(d+1,d+ans1+1,cmp);
    for(int i=1;i<=ans1;i++){
        if(r>=d[i].l) continue;
        ans2++,r=d[i].r;
    }
    cout<<m-ans2<<'\n';
}
signed main(){
    int T; cin>>T;
    while(T--) solve();
    return 0;
}
2024/11/26 15:43
加载中...