悬n关,90pts,WA #3求调
查看原帖
悬n关,90pts,WA #3求调
1046636
YFF1楼主2024/11/7 14:04
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m;
double len,speed,d[200005],a[200005],v[200005],p[200005]; 
struct node{
	int l,r;
}cho[200005];
bool cmp(node a,node b){
	if(a.r==b.r)return a.l<b.l;
	return a.r<b.r;
}
signed main () {
	cin>>t;
	while(t--){
		scanf("%lld%lld%lf%lf",&n,&m,&len,&speed);
		for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&d[i],&v[i],&a[i]);
		for(int i=1;i<=m;i++)scanf("%lf",&p[i]);
		int ans=0,cnt=0;
		for(int i=1;i<=n;i++){
			if(a[i]==0){
				if(v[i]>speed){
					int pos=lower_bound(p+1,p+1+m,d[i])-p;
					if(pos<=m&&pos>=1){
						cnt++;
						cho[cnt].l=pos;
						cho[cnt].r=m;
						ans++;
					}
					else continue;
				}
				else continue;
			}
			else if(a[i]>0){
				if(v[i]>speed){
					int pos=lower_bound(p+1,p+1+m,d[i])-p;
					if(pos>=1&&pos<=m){
						cnt++;
						cho[cnt].l=pos;
						cho[cnt].r=m;
						ans++;
					}
					else continue;
				}
				else {
					double fi=d[i]+(speed+v[i])*(speed-v[i])/(2*a[i]);
					int pos2=upper_bound(p+1,p+1+m,fi)-p;
					if(pos2<=m){
						ans++;
						cnt++;
						cho[cnt].l=pos2;
						cho[cnt].r=m;
					}
				}
			}
			else {
				if(v[i]>speed){
					double fi=d[i]+((speed-v[i])*(v[i]+speed))/(2*a[i]);
					int pos=lower_bound(p+1,p+1+m,fi)-p-1;
					int pos2=lower_bound(p+1,p+1+m,d[i])-p;
					if(pos>=1&&pos<=m&&pos2>=1&&pos2<=m&&pos2<=pos){
						ans++;
						cnt++;
						cho[cnt].l=pos2;
						cho[cnt].r=pos;
					}
				}
			}
		}
		sort(cho+1,cho+1+cnt,cmp);
		int pos=1,sum=1;
		for(int i=2;i<=cnt;i++){
			if(cho[i].l>cho[pos].r){
				pos=i;
				sum++;
			}
		}
		printf("%lld %lld\n",ans,m-sum);
	}
	return 0;
} 
2024/11/7 14:04
加载中...