60分求调
查看原帖
60分求调
468817
Nightsky_Stars楼主2024/10/29 08:00
#include<bits/stdc++.h>
using namespace std;
struct node{
	int l,r;
}b[100010];
int n,m,l,V,len,k,ans,d[100010],a[100010],v[100010],p[100010];
bool cmp(node x,node y){
	return x.r<y.r;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		k=ans=len=0;
		memset(a,0,sizeof(a));
		memset(d,0,sizeof(d));
		memset(v,0,sizeof(v));
		memset(p,0,sizeof(p));
		memset(b,0,sizeof(b));
		cin>>n>>m>>l>>V;
		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(d[i]>p[m]) continue;
			if(a[i]==0){
				if(d[i]<=p[m]&&v[i]>V){
					b[++len].l=lower_bound(p+1,p+1+m,d[i])-p;
					b[len].r=m;
				}
				continue;
			}
			if(a[i]>0&&v[i]>V){
				b[++len].l=lower_bound(p+1,p+1+m,d[i])-p;
				b[len].r=m;
				continue;
			}
			if(a[i]<0&&v[i]<=V) continue;
			double s=(V*V-v[i]*v[i])/2/a[i];
			if(a[i]>0){
				int h=s;
				if(h!=s) h++;
				if(d[i]+h>=p[m]) continue;
				b[++len].l=upper_bound(p+1,p+1+m,d[i]+h)-p;
				b[len].r=m;
			}else{
				int g=s,h=lower_bound(p+1,p+1+m,d[i])-p;
				if(g!=s) g++;
				if(d[i]+g<=p[h]) continue;
				b[++len].l=h;
				b[len].r=upper_bound(p+1,p+1+m,d[i]+g)-p-1;
				b[len].r=max(b[len].r,b[len].l);
			}
		}
		cout<<len<<" ";
		sort(b+1,b+1+len,cmp);
		for(int i=1;i<=len;i++){
			if(k>=b[i].l&&k<=b[i].r) continue;
			k=b[i].r;
			ans++;
		}
		ans=m-ans;
		cout<<ans<<"\n";
	}
	return 0;
}
2024/10/29 08:00
加载中...