90WA on #6
查看原帖
90WA on #6
643818
I_AK_CTS楼主2024/11/5 08:00
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
int T,n,m,L,V,d[N],v[N],a[N],p[N],s[N],e[N],S[N],E[N];
int G[N],cnt,flag[N];
bool cmp(int x,int y)
{
	if(S[x]!=S[y]) return S[x]<S[y];
	return E[x]<E[y];
}
signed main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		cnt=0;
		memset(flag,false,sizeof(flag));
		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];
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			if(v[i]<=V&&a[i]<=0) continue;
			if(a[i]==0)
			{
				s[i]=d[i];
				e[i]=L;
			}
			else if(a[i]>0&&v[i]>V)
			{
				s[i]=d[i];
				e[i]=L;
			}
			else
			{
				int o=(V*V-v[i]*v[i])/(2*a[i]);
				if((V*V-v[i]*v[i])%(2*a[i])==0)
				{
					if(a[i]<0) s[i]=d[i],e[i]=s[i]+o-1;
					else s[i]=d[i]+o+1,e[i]=L;
				}
				else
				{
					if(a[i]<0) s[i]=d[i],e[i]=s[i]+o;
					else s[i]=d[i]+o,e[i]=L;
				}
			}
			S[i]=lower_bound(p+1,p+1+m,s[i])-p;
			E[i]=upper_bound(p+1,p+1+m,e[i])-p-1;
			if(S[i]>E[i]) continue;
			ans++;
			G[++cnt]=i;
		}
		cout<<ans<<' ';
		sort(G+1,G+1+cnt,cmp);
		ans=0;
		int l,r;
		for(int i=1;i<=cnt;i++)
		{
//			cout<<S[G[i]]<<' '<<E[G[i]]<<'\n';
			if(i==1)
			{
				l=S[G[i]];
				r=E[G[i]];
				ans++;
				continue;
			}
			if(r<S[G[i]])
			{
				ans++;
				l=S[G[i]];
				r=E[G[i]];
			}
			else
			{
				r=min(r,E[G[i]]);
				l=max(l,S[G[i]]);
			}
		}
		cout<<m-ans<<'\n';
	}
	return 0;
}
/*
1
9 10 158022 5
65435 666 -3
1342 672 -2
10867 862 -8
110389 708 -9
1709 920 -8
130502 291 626
80612 947 -10
48629 783 -3
107502 903 -10
15014 53560 78649 88021 91322 104253 111591 117138 138176 152757
*/
2024/11/5 08:00
加载中...