20pts求助(玄关)
查看原帖
20pts求助(玄关)
1251345
2012_Zhang_楼主2024/11/9 13:25
#include<bits/stdc++.h>
using namespace std;
//d v a
struct z{
    int l,r;
}c[100005],nc[100005];
bool cmp(z x,z y){if(x.l!=y.l)return x.l<y.l; else return x.r>y.r;}
long long t,n,m,L,V,x[100005][5],p[100005],S[1000005],s2[1000005],tot,ttott,sum,o,oo=-1;
map<int,int>s;
bool f[100005];
int main(){
    cin>>t;
    while(t--){
        tot=0,ttott=0,sum=0;
        memset(S,0,sizeof S);
        cin>>n>>m>>L>>V;
        for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i][0],&x[i][1],&x[i][2]);
        for(int i=1;i<=m;i++) scanf("%lld",&p[i]),S[p[i]]=1;
        s[0]=0,s2[0]=-1;
        if(S[0]==1) s2[0]=0,s[0]=1;
        for(int i=0;i<=L;i++){
			s[i]=s[i-1]+S[i];
			s2[i]=s2[i-1];
			if(S[i]==1) s2[i]=i;
		}
        for(int i=1;i<=n;i++){
            if(x[i][2]==0){
                if(x[i][1]>V){
                    if(s[L]-s[x[i][0]-1]>0){
                        c[++tot].l=x[i][0],c[tot].r=L;
                    }
                }
            } 
            if(x[i][2]>0){
                int a=x[i][2];
                if((V*V-x[i][1]*x[i][1])/(2*a)+1+x[i][0]<=L){
                    if(s[L]-s[max((V*V-x[i][1]*x[i][1])/(2*a)+x[i][0],x[i][0]-1)]>0){
                        c[++tot].l=max((V*V-x[i][1]*x[i][1])/(2*a)+x[i][0],x[i][0]),c[tot].r=L;
                    }
                }
            }
            if(x[i][2]<0){
                int a=x[i][2];
                if(x[i][1]>=V){
                    if(s[min((x[i][1]*x[i][1]-V*V-1)/(-2*a)+x[i][0],L)]-s[x[i][0]-1]>0){
                        c[++tot].r=min((x[i][1]*x[i][1]-V*V-1)/(-2*a)+x[i][0],L);
                        c[tot].l=x[i][0];
                    }
                }
            }
        }
        cout<<tot<<' ';
        sort(c+1,c+tot+1,cmp);
        nc[++ttott].l=c[1].l,nc[1].r=c[1].r;
        for(int i=2;i<=tot;i++){
        	while(ttott>0&&nc[ttott].l<=c[i].l&&c[i].r<=nc[ttott].r) ttott--;
        	if(c[i].l>nc[ttott].l||ttott==0) nc[++ttott].l=c[i].l,nc[ttott].r=c[i].r,f[ttott]=false;
		}
		int j=2;
		for(int i=1;i<=ttott;i++){
			if(!f[i]){
				sum++;
				while(j<=ttott&&nc[j].l<=s2[nc[i].r]) f[j++]=true;
			}
		}
		cout<<m-sum<<endl;
    }
}
2024/11/9 13:25
加载中...