WA60pts求调(调好为义父)
查看原帖
WA60pts求调(调好为义父)
723816
XichenOC楼主2024/11/2 16:52

所有能过的都过了,就洛谷有4个测试点过不了,求大佬调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
struct car{
	int d,v,a;
}c[N];
struct edge{
	int l,r;
	bool operator<(const edge &a)const{return l<a.l;}
}e[N];
int dis[N],m,v;
int findn(int de){
	int l=1,r=m;
	while(l<r){
		int mid=(l+r)>>1;
		if(dis[mid]>=de)r=mid;
		else l=mid+1;
	}
	return l;
}
int findf(int de){
	int l=1,r=m;
	while(l<r){
		int mid=(l+r+1)>>1;
		if(v*v<2*c[de].a*(dis[mid]-c[de].d)+c[de].v*c[de].v)l=mid;
		else r=mid-1;
	}
	return l;
}
signed main(){ 
	//freopen("detect1.in","r",stdin);
	//freopen("detect.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		int n,l,cnt=0;
		cin>>n>>m>>l>>v;

		for(int i=1;i<=n;i++){
			cin>>c[i].d>>c[i].v>>c[i].a;
		}
		for(int i=1;i<=m;i++){
			cin>>dis[i];
		}
		for(int i=1;i<=n;i++){
			if(dis[m]>=c[i].d){
				if(c[i].a<=0 && c[i].v<=v)continue;
				else if(c[i].a>0 && c[i].v>v){
					int l=findn(c[i].d);
					cnt++;
					e[cnt]={l,m};
				}
				else if(c[i].a==0){
					int l=findn(c[i].d);
					cnt++;
					e[cnt]={l,m};
				}
				else if(c[i].a>0){
					l=findn(c[i].d+(v*v-c[i].v*c[i].v)/(2*c[i].a));
					if(v*v<2*c[i].a*(dis[m]-c[i].d)+c[i].v*c[i].v){
						cnt++;
						e[cnt]={l,m};
					}
				}
				else{
					int l=findn(c[i].d);
					int r=findf(i);
					if(v*v<2*c[i].a*(dis[l]-c[i].d)+c[i].v*c[i].v){
						cnt++;
						e[cnt]={l,r};
					}
				}
			}
		}
		int ans=0;
		sort(e+1,e+1+cnt);
		int minn=e[1].r;
		for(int i=1;i<=cnt;i++){
			//cout<<"########   "<<e[i].l<<" "<<e[i].r<<endl;
			if(e[i].l>minn){
				ans++;
				minn=e[i].r;
			}
			else{
				minn=min(minn,e[i].r);
			}
		}
		cout<<cnt<<" "<<m-ans-1<<endl;
	}
} 
2024/11/2 16:52
加载中...