s-t2,会挂吗
  • 板块学术版
  • 楼主furton_f
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/10/28 21:21
  • 上次更新2024/10/29 00:28:32
查看原帖
s-t2,会挂吗
1404571
furton_f楼主2024/10/28 21:21
#include<bits/stdc++.h>
using namespace std;
int t,n,m,L,xs,cnt;
int d[100050],v[100050],a[100050],p[100050];
bool chk(int i,int c){
	if(p[c]<d[i])return false;
	long long sum=0;
	sum=1LL*v[i]*v[i]+2LL*a[i]*(p[c]-d[i]);
	if(sum>1ll*xs*xs)return true;
	return false;
}
struct N{
	int ll,rr;
};
N c[100050];
bool cmp(N a,N b){
	if(a.rr!=b.rr)return a.rr<b.rr;
	else return a.ll<b.ll;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>L>>xs;
		for(int i=1;i<=n;i++){
			cin>>d[i]>>v[i]>>a[i];
		}
		for(int i=1;i<=m;i++){
			cin>>p[i];
		}
		sort(p+1,p+1+m);
		for(int i=1;i<=n;i++){
			if(a[i]==0){
				if(v[i]<=xs)continue;
				else{
					if(d[i]>p[m])continue;
					cnt++;
					int zdd=1,ydd=m,mb=-1;
					while(zdd<=ydd){
						int mid=(zdd+ydd)/2;
						if(p[mid]>d[i]){
							mb=mid;
							ydd=mid-1;
						}
						else zdd=mid+1;
					}
					c[cnt].ll=mb;
					c[cnt].rr=m;
				}
			}
			if(a[i]>0){
				if(d[i]>p[m])continue;
				int l=1,r=m,ans=-1;
				while(l<=r){
					int mid=(l+r)/2;
					if(chk(i,mid)){
						ans=mid;
						r=mid-1;
					}
					else l=mid+1;
				}
				if(ans==-1)continue;
				cnt++;
				c[cnt].ll=ans;
				c[cnt].rr=m;
			}
			if(a[i]<0){
				if(d[i]>p[m])continue;
				int zdd=1,ydd=m,mb=-1;
				while(zdd<=ydd){
					int mid=(zdd+ydd)/2;
					if(p[mid]>=d[i]){
						mb=mid;
						ydd=mid-1;
					}
					else zdd=mid+1;
				}
				if(chk(i,mb)==false)continue;
				cnt++;
				int l=mb,r=m,ans=-1;
				while(l<=r){
					int mid=(l+r)/2;
					if(chk(i,mid)){
						ans=mid;
						l=mid+1;
					}
					else r=mid-1;
				}
				c[cnt].ll=mb;
				c[cnt].rr=ans;
			}
		}
		cout<<cnt<<' ';
		sort(c+1,c+1+cnt,cmp);
		int last=-1,res=m;
		for(int i=1;i<=cnt;i++){
			if(c[i].ll>last){
				last=c[i].rr;
				res--;
			}
		}
		cout<<res<<'\n';
		cnt=0;
	}
	return 0;
}

2024/10/28 21:21
加载中...