90分求调
查看原帖
90分求调
1256176
CQnythy2012楼主2025/8/30 18:36

很玄幻,不知道哪里错了。

#include<bits/stdc++.h> 
using namespace std;
int t;
const int N=1e5+10;
struct Node{
	double d,v,a;
}x[N],y[N];
struct Node2{
	double left,right;
}g[N];
double p[N];
double ddd[N];
double dd,vv,aa;
int n,m,ans1,ans2=1;
double L,V;
int search1(int l,int r,double x){
	while(l<r){
		int mid=(l+r)/2;
		if(p[mid]<x){
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	return l;
}
int search2(int l,int r,double x){
	while(l<r){
		int mid=(l+r+1)/2;
		if(p[mid]<=x){
			l=mid;
		}
		else{
			r=mid-1;
		}
	}
	return l;
}
bool cmp(Node2 xx,Node2 yy){
	return xx.right<yy.right;
}
int main(){
//	freopen("detect.in","r",stdin);
//	freopen("detect.out","w",stdout);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d%lf%lf",&n,&m,&L,&V);
		int j=0,k=0,ll=0,o=0;
		for(int i=1;i<=n;i++){
			scanf("%lf%lf%lf",&dd,&vv,&aa);
			if(aa<0){
				y[++k].a=abs(aa);
				y[k].d=dd;
				y[k].v=vv;
			}
			else if(aa>0){
				x[++j].a=aa;
				x[j].d=dd;
				x[j].v=vv;
			}
			else{
				if(vv>V){
					ddd[++ll]=dd;
				}
			}
		}
		for(int i=1;i<=m;i++){
			scanf("%lf",&p[i]);
		}
		sort(p+1,p+1+m);
		for(int i=1;i<=ll;i++){
			if(ddd[i]<=p[m]){
				ans1++;
				g[++o].left=p[search1(1,m,ddd[i])];
				g[o].right=p[m];
			}
		}
		for(int i=1;i<=j;i++){
			if(p[m]<x[i].d){
				continue;
			}
			double ti=(0.0+V-x[i].v)*1.0/(1.0*x[i].a);
			double si=x[i].v*ti+0.5*ti*ti*1.0*x[i].a;
			if(si+x[i].d>=p[m]){
				continue;
			}
			else{
				ans1++;
			}
			int l=search1(1,m,si+x[i].d);
			if(p[l]==si+x[i].d){
				l++; 
			}
			g[++o].left=p[l];
			g[o].right=p[m];
		}
		for(int i=1;i<=k;i++){
			if(p[m]<y[i].d){
				continue;
			}
			if(V>y[i].v){
				continue;
			}
			double ti=(0.0+y[i].v-V)*1.0/(1.0*y[i].a);
			double si=y[i].v*ti-0.5*ti*ti*1.0*y[i].a;
			double r=y[i].d+si;
			double l=y[i].d;
			if(r<=p[search1(1,m,y[i].d)]||r<l){
				continue;
			}
			else{
				ans1++;
			}
			int rr=search2(1,m,y[i].d+si);
			if(p[rr]==y[i].d+si){
				rr--;
			}
			g[++o].left=p[search1(1,m,y[i].d)];
			g[o].right=p[rr];
		}
		sort(g+1,g+1+o,cmp);
		int now=1;
		for(int i=2;i<=o;i++){
			if(g[i].left>g[now].right){
				now=i;
				ans2++;
			}
		}
		printf("%d %d\n",ans1,m-ans2);
		ans1=0;
		ans2=1;
	}
	return 0;
}
2025/8/30 18:36
加载中...