WA一个!!
查看原帖
WA一个!!
1188691
liyuan2023楼主2024/10/30 20:59
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,m,l,k,p[N],ans1,ans2;
int d[N],v[N],a[N];
struct node{
	int l,r;
}c[N];
bool cmp(node a,node b){
	if(a.l!=b.l){
		return a.l<b.l;
	}
	return a.r>b.r;
}
int main(){
	cin>>t;
	while(t--){
		ans1=0,ans2=0;
		cin>>n>>m>>l>>k;
		for(int i=1;i<=n;i++){
			cin>>d[i]>>v[i]>>a[i];
		}
		for(int i=1;i<=m;i++){
			cin>>p[i];
		}
		for(int i=1;i<=n;i++){
			if(d[i]>p[m]||a[i]<=0&&v[i]<=k){
				continue;
			}
			if(a[i]>0&&k*k<v[i]*v[i]+2*a[i]*(p[m]-d[i])){
				ans1++;
				c[ans1].r=m;
				int ll=1,rr=m;
				while(ll<=rr){
					int mid=(ll+rr)/2;
					int x=v[i]*v[i]+2*a[i]*(p[mid]-d[i]);
					if(p[mid]>=d[i]&&k*k<x){
						rr=mid-1;
					}
					else{
						ll=mid+1;
					}
				}
				if(k*k<v[i]*v[i]+2*a[i]*(p[rr]-d[i])){
					c[ans1].l=rr;
				}
				else{
					c[ans1].l=ll;
				}
			}
			else if(a[i]<=0&&v[i]>k){
				int ll=1,rr=m;
				while(ll<=rr){
					int mid=(ll+rr)/2;
					if(p[mid]<d[i]){
						ll=mid+1;
					}
					else{
						rr=mid-1;
					}
				}
				if(p[rr]>=d[i]){
					ll=rr;
				}
				if(k*k<v[i]*v[i]+2*a[i]*(p[ll]-d[i])){
					ans1++;
					c[ans1].l=ll;
					if(ll==m||k*k<v[i]*v[i]+2*a[i]*(p[m]-d[i])){
						c[ans1].r=m;
						continue;
					}
					rr=m;
					while(ll<=rr){
						int mid=(ll+rr)/2;
						int x=v[i]*v[i]+2*a[i]*(p[mid]-d[i]);
						if(k*k<x){
							ll=mid+1;
						}
						else{
							rr=mid-1;
						}
					}
					if(k*k<v[i]*v[i]+2*a[i]*(p[ll]-d[i])){
						c[ans1].r=min(ll,m);
					}
					else{
						c[ans1].r=rr;
					}
				}
			}
		}
		sort(c+1,c+ans1+1,cmp);
		/*
		for(int i=1;i<=ans1;i++){
			cout<<c[i].l<<" "<<c[i].r<<endl;
		}
		*/
		int ll=-1,rr=m+1;
		for(int i=1;i<=ans1;i++){
			if(ll>c[i].r||rr<c[i].l){
				ans2++;
				ll=c[i].l,rr=c[i].r;
			}
			else{
				ll=max(ll,c[i].l);
				rr=min(rr,c[i].r);
			}
		}
		if(ll!=-1||rr!=m+1){
		    ans2++;
		}
		cout<<ans1<<" "<<m-ans2<<endl;
	}
    return 0;
}
2024/10/30 20:59
加载中...