90pts WA on #2 求调
查看原帖
90pts WA on #2 求调
761137
Double_Light楼主2024/11/11 21:41
#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int T;
int n,m,L,V;
struct node{
	int d,v,a;
}car[N];
int b[N],ans;
int c[N],d[N];
struct qj{
	int l,r,f;
}a[N];
int tot;
int cnt;
int f=1,f2=1;
bool cmp(qj x,qj y){
	if(x.l==y.l)return x.r<y.r;
	return x.l<y.l;
}
signed main(){
	//freopen("detect.in","r",stdin);
	//freopen("detect.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cnt=0;
		memset(c,0,sizeof(c));
		memset(d,0,sizeof(d));
		tot=0;ans=0;
		cin>>n>>m>>L>>V;
		for(int i=1;i<=n;i++){
			cin>>car[i].d>>car[i].v>>car[i].a;
		}
		for(int i=1;i<=m;i++)cin>>b[i];
		sort(b+1,b+m+1);
		for(int i=1;i<=n;i++){
			if(car[i].a>0){
				f=0;
				if(b[m]<car[i].d)continue;
				int l=0,r=m,mid,x;
				while(l<=r){
					mid=(l+r)/2;
					if(2*car[i].a*(b[mid]-car[i].d)+car[i].v*car[i].v>V*V){
						if(!c[i])ans++;
						c[i]=mid;
						r=mid-1;
					}
					else l=mid+1;
				}
				if(c[i])a[++tot]={c[i],m};
				d[m]++;c[i]=m;
			}
			if(car[i].a==0){
				f2=0;cnt++;
				int l=0,r=m,mid,x;
				while(l<=r){
					mid=(l+r)/2;
					if(b[mid]>=car[i].d){
						x=mid;
						r=mid-1;
					}
					else l=mid+1;
				} 
				if(b[m]<car[i].d)continue;
				if(car[i].v>V){
					ans++;
					a[++tot]={x,m};
				}
			}
			if(car[i].a<0){
				f=0;f2=0;
				int l=0,r=m,mid,x;
				while(l<=r){
					mid=(l+r)/2;
					if(b[mid]>=car[i].d){
						x=mid;
						r=mid-1;
					}
					else l=mid+1;
				} 
				if(-2*car[i].a*(b[x]-car[i].d)>car[i].v*car[i].v)continue;
				l=x,r=m; 
				while(l<=r){
					mid=(l+r)/2;
					if(2*car[i].a*(b[mid]-car[i].d)+car[i].v*car[i].v>V*V){
						if(!c[i])ans++;
						c[i]=mid;
						l=mid+1;
					}
					else r=mid-1;
				}
				if(c[i]){
					a[++tot]={x,c[i]};
					d[c[i]]++;
				}
			}
		}
		cout<<ans<<' ';
		if(f||f2){
			if(ans)cout<<m-1<<'\n';
			else cout<<m<<'\n';
			continue;
		}
		if(!ans){
			cout<<m<<'\n';
			continue;
		}
		sort(a+1,a+tot+1,cmp);
		ans=0;
		int l=1,minn=1e9;//cout<<endl;
		for(int i=1;i<=tot;i++){
			if(a[i].r>=a[i-1].r&&a[i].l<=a[i-1].l)a[i].f=1;
		}
		for(int i=1;i<=tot;i++){
			//cout<<a[i].l<<" "<<a[i].r<<' '<<a[i].f<<endl;
			if(a[i].f)continue;
			minn=min(minn,a[i].r);
			if(a[i].l>minn){
				//cout<<"i: "<<i<<' '<<minn<<endl;
				l=i;minn=a[l].r;
				ans++;
			}
		}
		ans++;
		cout<<m-ans<<'\n';
	}
	return 0;
}
/*
1
10 10 145322 772
10139 897 -47
86524 947 -2
51251 982 -2
12573 962 -2
14068 919 -163
10944 994 -6
35650 999 -9
3804 977 -1
1149 905 -2
43935 932 -2
10519 11805 14747 28890 37732 45509 55779 80531 108392 126659
*/
2024/11/11 21:41
加载中...