史上独一份 70pts 求调 无限悬关
查看原帖
史上独一份 70pts 求调 无限悬关
718487
CleverRaccoonʕ•ᴥ•ʔ楼主2025/2/3 20:21
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define File_IO(file)\
	freopen(file".in","r",stdin);\
	freopen(file".out","w",stdout);
#define rep(awa) for(int i=1;i<=(awa);i++)
#define up(qwq,x,y) for(int (qwq)=(x);(qwq)<=(y);(qwq)++)
#define down(qwq,x,y) for(int (qwq)=(x);(qwq)>=(y);(qwq)--)
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
#define mid ((l+r)/2)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lowbit(awa) ((awa)&(-(awa)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

const double eps=1e-9;
const int INF=0x7f7f7f7f;
const ll LLINF=0x7f7f7f7f7f7f7f7f;
const int SINF=0x3f3f3f3f;
const ll SLLINF=0x3f3f3f3f3f3f3f3f;
const int _INT_MAX_=2147483647;
const ll _LL_MAX_=9223372036854775807ll;

#define fast_IO

#ifdef fast_IO
ll read(){
	char ch=getchar();ll x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void print(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x<10)return putchar(x+'0'),void();
	print(x/10),putchar(x%10+'0');
}
#endif

const int N=1e5+7;
int n,m,l,v,cnt,ans,p[N],cho[N];
bool over[N],vis[N];
struct car{
	int d,v,a;
}c[N];
struct node{
	int l,r;
}can[N];

void init(){
#ifndef fast_IO
	cin.tie(nullptr)->sync_with_stdio(false);
#endif
}

void all_open(){
	ans=0;
	rep(n){
		if(c[i].d>p[m])continue;
		double speed;
		if(c[i].a==0){
			speed=c[i].v;
		}else if(c[i].a<0){
			int pos=lower_bound(p+1,p+m+1,c[i].d)-p;
			speed=sqrt(c[i].v*c[i].v+2*c[i].a*(p[pos]-c[i].d));
		}else{
			speed=sqrt(c[i].v*c[i].v+2*c[i].a*(p[m]-c[i].d));
		}
		if(speed>v)++ans,over[i]=1;
	}
	print(ans);
	putchar(' ');
}

void at_most(){
	// 如果车超过了p[m]或者没超速就不理他了
	// 以下只讨论超速的车
	// 对于加速的车,保留超速点最靠后的车的超速位置的超速检测,设为 G,则端点为 G~m
	// 对于匀速的车,最后一个超速点~m
	// 对于减速的车,从 d~最后一个超速点(速度降到v时)
	ans=0;
	rep(n){
		if(!over[i])continue;
		if(c[i].a>0){
			double s=(v*v-c[i].v*c[i].v)/2.0/c[i].a;
			can[++cnt].l=upper_bound(p+1,p+m+1,c[i].d+s)-p-1,can[cnt].r=m;
		}else if(c[i].a==0){
			can[++cnt].l=lower_bound(p+1,p+m+1,c[i].d)-p,can[cnt].r=m;
		}else{
			int l=lower_bound(p+1,p+m+1,c[i].d)-p;
			double s=(v*v-c[i].v*c[i].v)/2.0/c[i].a;
			int r=lower_bound(p+1,p+m+1,c[i].d+s)-p-1;
			can[++cnt].l=l,can[cnt].r=r;
		}
	}
	sort(can+1,can+cnt+1,[](const node &a,const node &b){
		if(a.r==b.r)return a.l<b.l;
		return a.r<b.r;
	});
//	cout<<'\n';
//	rep(cnt){cout<<can[i].l<<' '<<can[i].r<<'\n';}
	rep(cnt){
		bool flag=0;
		up(j,1,ans)if(can[i].l<=cho[j]&&cho[j]<=can[i].r){
			flag=1;
			break;
		}
		if(!flag)cho[++ans]=can[i].r;
	}
	print(m-ans);
}

void solve(){
	n=read(),m=read(),l=read(),v=read();
	rep(n)c[i].d=read(),c[i].v=read(),c[i].a=read();
	rep(m)p[i]=read();
	memset(over,0,sizeof over);
	memset(vis,0,sizeof vis);
	cnt=0;
	all_open();
	at_most();
	puts("");
//	puts("");
}

int main(){
//	freopen("detect\\detect2.in","r",stdin);
	init();
	int T=1;
	T=read();
//  cin>>T;
	rep(T)solve();
	return 0;
}

2025/2/3 20:21
加载中...