90分求调
查看原帖
90分求调
752092
Yeefung楼主2024/11/2 09:37
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n,m,L,V,p[N];
bool vis[N],viss;
struct node{
	int d,v,a;
}c[N];
struct NODE{
	int l,r;
}w[N];
bool cmp(NODE x,NODE y){
	if(x.r==y.r)return x.l<y.l;
	return x.r<y.r; 
}
signed main(){
//	freopen("detect.in","r",stdin);
//	freopen("detect.out","w",stdout);
	int T;
	scanf("%lld",&T);
	while(T--){
		memset(vis,0,sizeof(vis));
		viss=0;
		int ans=0,cnt=0,cntf=0;
		scanf("%lld%lld%lld%lld",&n,&m,&L,&V);
		
		for(int i=1;i<=n;i++){
			scanf("%lld%lld%lld",&c[i].d,&c[i].v,&c[i].a);
			
		}	
		for(int i=1;i<=m;i++){
			scanf("%lld",&p[i]);
		}
		for(int i=1;i<=n;i++){
			if(c[i].d>p[m])continue;
			if(c[i].a>=0){
				int s=p[m]-c[i].d;
				if(c[i].v*c[i].v+2*c[i].a*s>V*V){
					viss=true;
					ans++;
					int l=1,r=m;
				while(l<=r){
					int mid=l+r>>1;
					int s=p[mid]-c[i].d;
					if(s<0)l=mid+1;
					else{
						if(c[i].v*c[i].v+2*c[i].a*s<=V*V)l=mid+1;
						else r=mid-1;
					}
					
				}
					w[0].l=max(w[0].l,l);
					w[0].r=m;
				}
			}
			if(c[i].a<0){
				bool flag=false;
				int l=1,r=m,minn;
				while(l<=r){
					int mid=l+r>>1;
					if(p[mid]<c[i].d)l=mid+1;
					else r=mid-1;
				}
				minn=l,r=m;
				while(l<=r){
					int mid=l+r>>1;
					int s=p[mid]-c[i].d;
					if(c[i].v*c[i].v+2*c[i].a*s>V*V)l=mid+1,flag=true;
					else r=mid-1;
					
				}
				if(flag){
					ans++;
					w[++cntf].r=r;
					w[cntf].l=minn;
				}
			}
		
		}
		sort(w+1,w+cntf+1,cmp);
		for(int i=viss?0:1;i<=cntf;i++){
			bool flag=false;
			for(int j=w[i].l;j<=w[i].r;j++){
				if(vis[j]){
					flag=true;
					break;
				}
			}
			if(!flag)vis[w[i].r]=true,cnt++;
		}
		printf("%lld %lld\n",ans,m-cnt);
	}
	return 0;
} 
2024/11/2 09:37
加载中...