20分,求调
查看原帖
20分,求调
1243205
0720wangyuxiang楼主2024/11/22 20:43
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int T;
int n,m,L,V;
int d[N],v[N],p[N],a[N];
int l[N],r[N];
struct node{
	int al,ar;
}aa[N];
bool cmp(node x,node y){
	return x.ar<y.ar;
}
signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m>>L>>V;
		int ans=0;
		for(int i=1;i<=n;i++)cin>>d[i]>>v[i]>>a[i];
		for(int i=1;i<=m;i++)cin>>p[i];
		for(int i=1;i<=n;i++)l[i]=r[i]=0;
		for(int i=1;i<=n;i++){
			//表示在l[i]<=x<r[i]时超速
			double ll,rr;
			if(a[i]<0){//匀减速运动
				if(v[i]<=V){
					l[i]=r[i]=-1;
				    continue;
				}//不可能超速
				int l4=d[i],r4=L;
				while(l4<r4){
					int mid=(l4+r4+1)/2;
					if(v[i]*v[i]+2*a[i]*(mid-d[i])<=V*V)r4=mid-1;
					else l4=mid;
				}
				if(v[i]*v[i]+2*a[i]*(l4-d[i])<=V*V){
					l[i]=r[i]=-1;
					continue;
				}
				ll=d[i];//违法行驶路段
				rr=l4;
				int lll=1,rrr=m;
				while(lll<rrr){
					int mid=(lll+rrr)/2;
					if(p[mid]<ll)lll=mid+1;
					else rrr=mid;
				}
				if(p[lll]<ll||p[lll]>rr){
					l[i]=r[i]=-1;
					continue;
				}
				l[i]=lll;
				lll=1;
				rrr=m;
				while(lll<rrr){
					int mid=(lll+rrr+1)/2;
					if(p[mid]>rr)rrr=mid-1;
					else lll=mid;
				}
				r[i]=lll;
				//cout<<l[i]<<' '<<r[i]<<'\n';
			}
			else if(a[i]==0){//匀速直线运动
				if(v[i]<=V){
					l[i]=r[i]=-1;
					//cout<<l[i]<<' '<<r[i]<<'\n';
					continue;
				}
				ll=d[i];//违法行驶路段
				rr=L+1;
				int lll=1,rrr=m;
				while(lll<rrr){
					int mid=(lll+rrr)/2;
					if(p[mid]<ll)lll=mid+1;
					else rrr=mid;
				}
				if(p[lll]<ll){
					l[i]=r[i]=-1;
				}
				l[i]=lll;
				r[i]=m;
				//cout<<l[i]<<' '<<r[i]<<'\n';
			}
			else{//匀加速运动
				if(v[i]>V){
					l[i]=d[i];
					r[i]=L+1;
					//cout<<l[i]<<' '<<r[i]<<'\n';
					continue;
				}
				double s=(1.0*V*V-1.0*v[i]*v[i])/(1.0*2*a[i]);
				if(s==signed(s))s+=0.1;
				ll=d[i]+s;
				rr=L+1;
				int lll=1,rrr=m;
				while(lll<rrr){
					int mid=(lll+rrr)/2;
					if(p[mid]<ll)lll=mid+1;
					else rrr=mid;
				}
				if(p[lll]<ll){
					l[i]=r[i]=-1;
				}
				l[i]=lll;
				r[i]=m;
				//cout<<i;
				//cout<<p[l[i]]<<' '<<p[r[i]]<<'\n';
			}
			if(l[i]!=-1){
				aa[++ans].al=l[i];
				aa[ans].ar=r[i];
			}
		}
		cout<<ans<<' ';
		int cnt=ans;
		sort(aa+1,aa+1+cnt,cmp);
		ans=0;
		int r5=0;
		for(int i=1;i<=cnt;i++){
			if(aa[i].al<=r5)continue;
			r5=aa[i].ar;
			ans++;
		}
		cout<<m-ans;
		cout<<'\n';
	}
	return 0;
}
2024/11/22 20:43
加载中...