70pts求条 WAon 1,5,6玄关
查看原帖
70pts求条 WAon 1,5,6玄关
519276
W_Sibo楼主2024/11/1 20:16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int N=1e5+10,M=1e6+10;
const double eps=1e-10;
ll t,n,m,l,vl,d[N],v[N],a[N],ans=0,cnt=0,nearest[M],p[N];
struct edge{
	ll x,y;
	friend bool operator<(const edge a,const edge b){
		if(a.y==b.y) return a.x<b.x;
		return a.y<b.y;
	}
}e[N];
int main(){
	//freopen("detect4.in","r",stdin);
	cin>>t;
	while(t--){
		cin>>n>>m>>l>>vl;
		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 j=p[i-1];j<p[i];j++){
				nearest[j]=p[i-1];
			}
		}
		for(int j=p[m];j<=l;j++){
			nearest[j]=p[m];
		}
		for(int i=1;i<=n;i++){
			if(a[i]==0){
				if(v[i]>vl){
					if(nearest[l]<d[i]) continue;
					e[++cnt].x=d[i];
					e[cnt].y=l;
				}
			}else{
				if(a[i]>0){
					ld rt=(ld)(vl-v[i])/(ld)(a[i]);
					ld rp=(ld)(v[i])*rt+0.5*(ld)(a[i])*rt*rt+eps+(ld)d[i];
					if(rp>(ld)l) continue;
					ll st=max((ll)(ceil(rp)),d[i]);
					if(nearest[l]<st) continue;
					e[++cnt].x=st;
					e[cnt].y=l;
				}else{
					ld rt=(ld)(vl-v[i])/(ld)(a[i]);
					ld rp=(ld)(v[i])*rt+0.5*(ld)(a[i])*rt*rt-eps+(ld)d[i];
					if(rp<(ld)d[i]) continue;
					ll ed=min((ll)(floor(rp)),l);
					if(nearest[ed]<d[i]) continue;
					e[++cnt].x=d[i];
					e[cnt].y=ed;
				}
			}
		}
		cout<<cnt<<' ';
		sort(e+1,e+cnt+1);
		ans=1;
		ll left=e[1].x,right=e[1].y;
		for(int i=2;i<=cnt;i++){
			left=max(left,e[i].x);
			if(nearest[right]<left||left>right){
				ans++;
				right=e[i].y;
				left=e[i].x;
			}
		}
		ans=m-ans;
		cout<<ans<<'\n';
		memset(d,0,sizeof d);
		memset(v,0,sizeof v);
		memset(a,0,sizeof a);
		memset(p,0,sizeof p);
		memset(nearest,0,sizeof nearest);
		ans=cnt=n=m=l=vl=0;
	}
}
2024/11/1 20:16
加载中...