天问,60pts求调
查看原帖
天问,60pts求调
1379970
mankinds楼主2024/10/31 17:55
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+2 , M=1e6+2;
int T , n , m , l , V , tmp , ans=0 , sum=0;
int d[N] , v[N] , a[N] , p[N];
int lt[M] , rt[M];
int le[N] , ri[N];
int w[N];
int is=-1;
bool S(int x,int y) {
	if(ri[x]==ri[y]) {
		return le[x]>le[y];
	}
	return ri[x] < ri[y];
}
void judge() {
	cin >> n >> m >> l >> V;
	for(int i=1; i<=n; i++) {
		cin >> d[i] >> v[i] >> a[i];
	}
	for(int i=1; i<=m; i++) {
		cin >> p[i];
		lt[p[i]]=rt[p[i]]=i;
	}
	p[0]=0;
	p[m+1]=l+1;
	for(int i=0; i<m; i++) {
		for(int j=p[i]+1; j<p[i+1]; j++) {
			lt[j]=i;
			rt[j]=i+1;
		}
	}
	for(int i=1; i<=n; i++) {
		if(d[i]>p[m]) {
			continue;
		}
		if(a[i]==0) {
			if(v[i]>V) {
				w[++ans]=i;
				le[i]=rt[d[i]];
				ri[i]=m;
			}
		} else if(a[i]>0) {
			if(v[i]>V) {
				w[++ans]=i;
				le[i]=rt[d[i]];
				ri[i]=m;
			} else {
				tmp=V*V-v[i]*v[i];
				if(tmp%(2*a[i])==0) {
					tmp=d[i]+tmp/(2*a[i]);
					if(tmp<p[m]) {
						w[++ans]=i;
						le[i]=rt[d[i]];
						ri[i]=m;
					}
				} else {
					tmp=d[i]+tmp/(2*a[i])+1;
					if(tmp<=p[m]) {
						w[++ans]=i;
						le[i]=rt[d[i]];
						ri[i]=m;
					}
				}
			}
		} else {
			if(v[i]>V) {
				tmp=v[i]*v[i]-V*V;
				if(tmp%(-2*a[i])==0) {
					tmp=d[i]+tmp/(-2*a[i]);
					if(tmp>p[m]) {
						w[++ans]=i;
						le[i]=rt[d[i]];
						ri[i]=m;
					} else {
						le[i]=rt[d[i]];
						ri[i]=lt[tmp-1];
						if(ri[i]>=le[i]) {
							w[++ans]=i;
						}
					}
				} else {
					tmp=d[i]+tmp/(-2*a[i]);
					if(tmp>p[m]) {
						w[++ans]=i;
						le[i]=rt[d[i]];
						ri[i]=m;
					} else {
						le[i]=rt[d[i]];
						ri[i]=lt[tmp-1];
						if(ri[i]>=le[i]) {
							w[++ans]=i;
						}
					}
				}
			}
		}
	}
	sort(w+1,w+ans+1,S);
	for(int i=1; i<=ans; i++) {
		if(le[w[i]]>is) {
			is=ri[w[i]];
			++sum;
		}
	}
	if(ans==0) {
		cout << 0 << " " << m << endl;
	} else {
		cout << ans << " " << m-sum << endl;
	}
}
int main() {
	freopen("detects.in","r",stdin);
	freopen("detects.out","w",stdout);
	cin >> T;
	while(T--) {
		judge();
	}
	return 0;
}
2024/10/31 17:55
加载中...