90pts求调
查看原帖
90pts求调
468817
Nightsky_Stars楼主2024/11/9 11:43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 -2
6 4 -4
2 5 8 9 15
*/
struct node{
	ll l,r;
}f[100010];
bool cmp(node x,node y){
	if(x.r==y.r){
		return x.l<y.l;
	}
	return x.r<y.r;
}
ll v[100010],p[100010],d[100010],a[100010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin>>t;
	while(t--){
		ll n,m,L,V,ans=0ll,len=0ll;
		cin>>n>>m>>L>>V;
		for(ll i=1;i<=n;i++){
			cin>>d[i]>>v[i]>>a[i];
		}
		for(ll i=1;i<=m;i++){
			cin>>p[i];
		}
		sort(p+1,p+1+m);
		for(ll i=1;i<=n;i++){
			if(d[i]>p[m]) continue;
			if(a[i]==0){
				if(v[i]>V&&d[i]<=p[m]){
					len++;
					f[len].l=lower_bound(p+1,p+1+m,d[i])-p;
					f[len].r=m;
				}	
				continue;
			}
			if(v[i]<=V&&a[i]<0) continue;
			if(v[i]>V&&d[i]<=p[m]&&a[i]>0){
				len++;
				f[len].l=lower_bound(p+1,p+1+m,d[i])-p;
				f[len].r=m;
				continue;
			}
			long double s=1.00*(V*V-v[i]*v[i])/2/a[i];
			if(a[i]>0){
				ll h=s;
				if(d[i]+h>=p[m]) continue;
				if(h!=s) h++;
				len++;
				f[len].l=lower_bound(p+1,p+1+m,d[i]+s)-p;
				f[len].r=m;
			}else{
				ll h=lower_bound(p+1,p+1+m,d[i])-p,g=s;
				if(g!=s) g++;
				if(d[i]>=p[m]||d[i]+g<=p[h]) continue;
				len++;
				f[len].l=h;
				f[len].r=lower_bound(p+1,p+1+m,d[i]+s)-p-1;
				f[len].r=max(f[len].r,f[len].l);
			}
		}
		cout<<len<<" ";
		ans=0;
		sort(f+1,f+1+len,cmp);
		ll p=0;
		for(ll i=1;i<=len;i++){
			if(p>=f[i].l&&p<=f[i].r){
				continue;
			}
			p=f[i].r;
			ans++;
		}
		ans=m-ans;
		cout<<ans<<"\n";
	}
	return 0;
}
2024/11/9 11:43
加载中...