70求调,或可能出现什么问题
查看原帖
70求调,或可能出现什么问题
1220004
_moting_楼主2024/10/28 18:57

民间数据WA on #1#8#10,官方大样例5出现了可以关掉的测速仪变多的情况qwq

#include<bits/stdc++.h>
#define int long long
#define db double
using namespace std;

const int N=1e5+10;

struct edge{
	int l,r;
}b[N],c[N],f[N];

int t,n,m,L,V;
int d,v,a;
int p[N];

int read(){
	int x=0,f=1;
	char ch=getchar();
	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(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		print(x/10);
	}
	putchar(x%10+'0');
	return;
}

int downn(db x){
	int ans=x-0.00000001;
	return ans;
}

bool cmp(edge x,edge y){
	if(x.l==y.l)return x.r>y.r;
	return x.l<y.l;
}

void solve(){
	n=read();
	m=read();
	L=read();
	V=read();
	int cnt=0;
	int tot=0;
	for(int i=1;i<=n;i++){
		d=read();
		v=read();
		a=read();
		if(a==0){
			if(v>V){
				b[++cnt].l=d;
				b[cnt].r=L;
			}
		}
		if(a>0){
			if(v>V){
				b[++cnt].l=d;
				b[cnt].r=L;
			}
			else{
				int x=(V*V-v*v)/2/a+1;
				x+=d;
				if(x<=L){
					b[++cnt].l=x;
					b[cnt].r=L;
				}
			}
		}
		if(a<0){
			if(v>V){
				b[++cnt].l=d;
				b[cnt].r=min((V*V-v*v)/2/a+d,L);
			}
		}
	}
	for(int i=1;i<=m;i++){
		p[i]=read();
	}
	sort(p+1,p+1+m);
	int ans=0;
	for(int i=1;i<=cnt;i++){
		int x=lower_bound(p+1,p+1+m,b[i].l)-p;
		if(p[x]<=b[i].r&&p[x]>=b[i].l){
			ans++;
			c[++tot].l=b[i].l;
			c[tot].r=b[i].r;
		}
	}
	print(ans);
	cout<<' ';
	cnt=0;
	sort(c+1,c+1+tot,cmp);
	for(int i=tot,j=tot;i;i--){
		while(c[i].r<=c[j-1].r&&j>1){
			j--;
		}	
		f[++cnt].l=c[i].l;
		f[cnt].r=c[i].r;
		i=j;
	}
	int s=0;
	ans=0;
	sort(f+1,f+1+cnt,cmp);
	p[m+1]=1e9;
	s=upper_bound(p+1,p+2+m,f[1].r)-p;
	for(int i=1;i<=cnt;i++){
		if(p[s]>=f[i].l&&p[s]<=f[i].r)continue;
		s=upper_bound(p+1,p+2+m,f[i].r)-p;
		s--;
		ans++;
	}
	print(m-ans);
	cout<<"\n";
}

signed main(){
//	freopen("detect5.in","r",stdin);
//	freopen("detect5.out","w",stdout);
	t=read();
	while(t--)solve();
}
2024/10/28 18:57
加载中...