70pts,求条
查看原帖
70pts,求条
845988
Shizaki_Crazy_Three楼主2024/10/28 08:09

rt

#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int cnt,tot;
int T;
int n,m,L,V;
struct node{
    int d,v,a;
}a[N];
struct op{
    int l,r;
    int flag=0;
}b[N],e[N];

inline bool cmp(op a,op b){
    if(a.l!=b.l) return a.l<b.l;
    return a.r<b.r;
}

inline bool cmp1(op a,op b){
    if(a.r!=b.r) return a.r<b.r;
    return a.l<b.l;
}
int p[N];
int vis[N];
int main(){
    scanf("%d",&T);
    while(T--){
        cnt=0;
        memset(b,0,sizeof b);
        memset(e,0,sizeof e);
        scanf("%d%d%d%d",&n,&m,&L,&V);
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&a[i].d,&a[i].v,&a[i].a);
            if(a[i].a>0){
                int x=(V*V-a[i].v*a[i].v+(2*a[i].v-1))/(2*a[i].a);
                if(a[i].d+x<=L){
                    b[++cnt].l=max(a[i].d,a[i].d+x);
                    b[cnt].r=L;
                }
            }else if(a[i].a<0){
                if(a[i].v<=V) continue;
                int x=(V*V-a[i].v*a[i].v)/(2*a[i].a);
                b[++cnt].l=a[i].d;
                b[cnt].r=min(L,a[i].d+x); 
            }else{
                if(a[i].v<=V) continue;
                b[++cnt].l=a[i].d;
                b[cnt].r=L;
            }
        }
        sort(b+1,b+cnt+1,cmp);
        int sum=0;
        int ans=0;
        memset(vis,0,sizeof vis);
        for(int i=1,j=1;i<=m;i++){
            scanf("%d",&p[i]);
            for(;j<=cnt;j++){
                if(p[i]>=b[j].l&&p[i]<=b[j].r){
                    sum++;
                    b[j].flag=1;
                }
                if(p[i]<b[j].l){
                    break;
                }
            }
        }
        
        tot=0;
        for(int i=1;i<=cnt;i++){
            if(!b[i].flag) continue;
            e[++tot].l=b[i].l;
            e[tot].r=b[i].r;
         //   cout<<e[tot].l<<' '<<e[tot].r<<endl;
        }ans=0;printf("%d ",tot);
        sort(e+1,e+tot+1,cmp1);
        for(int i=1,j=1;i<=m&&j<=tot;i++){
            int L=i,R=m,mid,res;
            while(L<=R){
                mid=(L+R+1)>>1;
                if(p[mid]<=e[j].r){
                    L=mid+1;
                    res=mid;
                }else R=mid-1;
            }
            i=res;
            for(;j<=tot;j++){
                if(p[i]>=e[j].l&&p[i]<=e[j].r){
                    if(!vis[i]) ans++;
                    vis[i]=1;
                }
                if(p[i]<e[j].l){
                    break;
                }
            }
        }
        printf("%d\n",m-ans);
    }
    return 0;
}
2024/10/28 08:09
加载中...