蒟蒻50pts求助悬赏50RP
查看原帖
蒟蒻50pts求助悬赏50RP
473401
zcxnb楼主2024/10/27 14:10
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int T,n,m,L,V,d,v,a,tot,num,cnt,ans;
int sum[M],q[N];
struct sb{
	int l,r;
}duan[N];
struct dot{
	int l,r,co;
}tr[N];
int query(int d,int v,int a){
	double x=V*V-v*v;
	double z=x/(double)(2*a);
	int y;
	if(a>0){
		y=(int)floor(z)+1;
	}
	else{
		y=(int)ceil(z)-1;
	}
	return d+y;
}
bool cmp(dot x,dot y){
	if(x.r==y.r)  return x.l<y.l;
	return x.r<y.r;
}
int main(){
	scanf("%d",&T);
	while(T--){
		ans=tot=cnt=0;
		scanf("%d%d%d%d",&n,&m,&L,&V);
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&d,&v,&a);
			if(a==0){
				if(v>V){
					duan[++tot]={d,L};
				}
			}
			else if(a>0){
				if(v>V){
					duan[++tot]={d,L};
				}
				else{
					int to=query(d,v,a);
					if(to<=L){
						duan[++tot]={to,L};
					}
				}
			}
			else{
				duan[++tot]={d,min(query(d,v,a),L)};
			}
		}
		for(int i=1;i<=m;i++){
			scanf("%d",&q[i]);
		}
		sum[0]=0;
		for(int i=0,j=1;i<=L;i++){
			if(i)  sum[i]=sum[i-1];
			while(j<=m&&q[j]==i)  sum[i]++,j++;
		}
		for(int i=1;i<=tot;i++){
			int cl,cr;
			if(duan[i].l)  cl=sum[duan[i].l-1];
			else  cl=0;
			cr=sum[duan[i].r];
			if(cl==cr)  continue;
			tr[++cnt]={duan[i].l,duan[i].r,cr};
		}
		sort(tr+1,tr+1+cnt,cmp);
		int lst=-1;
		for(int i=1;i<=cnt;i++){
			if(tr[i].l<=lst)  continue;
			ans++;
			lst=q[tr[i].co];
		}
		printf("%d %d\n",cnt,m-ans);
	}
}
2024/10/27 14:10
加载中...