P11232,WA#8,#10,应该是a[i]<0的问题,求调

学术版

Lycdeer @ 2024-11-29 20:50:47

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,tmp;
double L,V,d[N],v[N],a[N],p[N];
struct node{
    int l,r;
}x[N];
bool cmp(node b,node c){
    if(b.r==c.r) return b.l<c.l;
    return b.r<c.r;
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin>>T;
    while(T--){
        for(int i=1;i<=tmp;i++) x[i].l=x[i].r=0;
        tmp=0;
        cin>>n>>m>>L>>V;
        for(int i=1;i<=n;i++) cin>>d[i]>>v[i]>>a[i];
        for(int i=1;i<=m;i++) cin>>p[i];
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            if(d[i]>p[m]) continue;
            if(v[i]<=V&&a[i]<=0) continue;
            if(v[i]>V&&a[i]>=0){
                ans1++;
                x[++tmp].l=lower_bound(p+1,p+m+1,d[i])-p; x[tmp].r=m;
                continue;
            }
            long long bcs=V*V-v[i]*v[i],cs=2*a[i];
            double s=(double)bcs/(double)cs+(double)d[i];
            if(a[i]>0&&s>=p[m]) continue;
            if(a[i]<0&&p[lower_bound(p+1,p+m+1,d[i])-p]>=s) continue;
            if(a[i]>0) x[++tmp].l=upper_bound(p+1,p+m+1,s)-p,x[tmp].r=m;
            else x[++tmp].l=lower_bound(p+1,p+m+1,d[i])-p,x[tmp].r=upper_bound(p+1,p+m+1,s)-p-1;
            ans1++;
        }
        sort(x+1,x+tmp+1,cmp);
        int las=0;
        for(int i=1;i<=tmp;i++)
            if(x[i].l>las) ans2++,las=x[i].r;
        cout<<ans1<<' '<<m-ans2<<'\n';
    }
    return 0;
}

|