40pts求调
查看原帖
40pts求调
1142472
Wsb101355楼主2025/7/31 19:48
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
ll t,n,m,l,vc,p[N];
struct node{
	ll d,v,a,edd,beg,vis;
}car[N];
bool cmp(node a,node b){
	return a.edd<b.edd;
}
int main(){
	cin>>t;
	while(t--){
		cin>>n>>m>>l>>vc;
		for(int i=1;i<=n;i++){
			cin>>car[i].d>>car[i].v>>car[i].a;
			
			
		}
		for(int i=1;i<=m;i++){
			cin>>p[i];
		}
		p[m+1]=-1;
		ll ans=0;
		for(int i=1;i<=n;i++){
			if(car[i].a>0){
				if(car[i].v>vc){
					car[i].beg=p[lower_bound(p+1,p+1+m,car[i].d)-p];
					car[i].edd=p[m];
					
				}else{
					double s=double(car[i].d)+double(0.5*(vc*vc-car[i].v*car[i].v)/car[i].a);
					car[i].beg=p[upper_bound(p+1,p+1+m,s)-p];
					car[i].edd=p[m];
				}
			}if(car[i].a<=0){
				if(car[i].v>vc){
					if(car[i].a!=0){
						
						double s=double(car[i].d)+double(0.5*(vc*vc-car[i].v*car[i].v)/car[i].a);

						car[i].beg=p[lower_bound(p+1,p+1+m,car[i].d)-p];
						car[i].edd=p[lower_bound(p+1,p+1+m,s)-p-1];						
					}else{
						/*if(i==2){
							cout<<car[i].d<<" "<<lower_bound(p+1,p+1+m,car[i].d)-(p+1);
						}*/
						car[i].beg=p[lower_bound(p+1,p+1+m,car[i].d)-p];
						car[i].edd=p[m];							
					}

					
				}else{
					car[i].beg=0;;
					car[i].edd=-1;
				}
			}
			
			

			if(car[i].edd>=car[i].beg){
				ans++;
			}
		}
		cout<<ans<<" ";
		sort(car+1,car+1+n,cmp);
		ans=0;
		int tot=0;
		for(int i=1;i<=n;i++){
			if(car[i].edd<car[i].beg){
				continue;
			}
			if(tot<car[i].beg){
				ans++;
				tot=car[i].edd;
			}	
		}
		cout<<m-ans<<"\n";
		
	}
	
	
	return 0;
}
2025/7/31 19:48
加载中...