90pts 求 hack
查看原帖
90pts 求 hack
504093
dyc2022楼主2024/10/31 17:31

rt,WA on #8 求 hack。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 1000006
using namespace std;
int T,n,m,L,V,p[N],sum[N],ans1,ans2,near[N];
struct Seg{int l,r;};
bool operator <(Seg x,Seg y){return x.r<y.r;}
vector<Seg> vc;
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();
	return ret*f;
}
inline void write(int k)
{
	if(k<0)putchar('-'),k=-k;
	int nnum[20],ttp=0;
	while(k)nnum[++ttp]=k%10,k/=10;
	if(!ttp)nnum[++ttp]=0;
	while(ttp)putchar(nnum[ttp--]^48);
}
signed main()
{
	//freopen("detect.in","r",stdin);
	//freopen("detect.out","w",stdout);
	T=read();
	while(T--)
	{
		n=read(),m=read(),L=read(),V=read(),ans1=ans2=0;
		vc.clear();
		for(int i=1;i<=L;i++)sum[i]=near[i]=0;
		for(int i=1;i<=n;i++)
		{
			int d=read(),v=read(),a=read(),l=-1,r=-1;
			if(fabs(a)<=eps){if(v>V)l=d,r=L;}
			else if(a<0)
			{
				double end_pos=d*1.0+(1.0*V*V-1.0*v*v)/(2.0*a);
				if(end_pos>=1.0*d)l=d,r=min((int)ceil(end_pos)-1,L);
			}
			else
			{
				double start_pos=d*1.0+(1.0*V*V-1.0*v*v)/(2.0*a);
				if(start_pos<=1.0*L)l=max(d,(int)floor(start_pos)+1),r=L;
			}
			if(~l&&~r)vc.push_back({l,r});
		}
		for(int i=1;i<=m;i++)sum[p[i]=read()]++,near[p[i]]=p[i];
		for(int i=2;i<=L;i++)sum[i]+=sum[i-1],near[i]=max(near[i-1],near[i]);
		for(Seg sg:vc)ans1+=sum[sg.r]-sum[sg.l-1]>0;
		sort(vc.begin(),vc.end());
		int pos=-1;
		for(Seg sg:vc)
		{
			if(sg.l<=pos&&pos<=sg.r)continue;
			if(sum[sg.r]-sum[sg.l-1]<=0)continue;
			ans2++,pos=near[sg.r];
		}
		write(ans1),putchar(' '),write(m-ans2),putchar('\n');
	}
	return 0;
}
2024/10/31 17:31
加载中...