60pt后四个wa求调
查看原帖
60pt后四个wa求调
316533
why100楼主2024/11/8 09:22
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const double Ex = 1e-12;
const int N = 1e5+1000;
int d,v,a,p[N],cl[N],cr[N],w[N];
int t,n,m,l,vl,beg,cnt,tac,ans;
bool vis[N];
void init()
{
	memset(vis,0,sizeof(vis));
//	memset(d,0,sizeof(d));
//	memset(v,0,sizeof(v));
//	memset(a,0,sizeof(a));
	memset(p,0,sizeof(p));
}
bool cmp(int a,int b)
{
	if(cr[a] == cr[b])
	{
		return cl[a] < cl[b]; 
	}
	return cr[a] < cr[b];
}
signed main()
{
//	freopen("detect.in","r",stdin);
//	freopen("detect.out","w",stdout);
	scanf("%lld",&t);
	while(t--)
	{
		init();
		scanf("%lld %lld %lld %lld",&n,&m,&l,&vl);
//		if(n == (int)1e5)abort(); 
		for(int i = 1;i <= n;i++)
		{
			w[i] = i;//间接排序数组 
			scanf("%lld %lld %lld",&d,&v,&a);
			cl[i] = cr[i] = -1;
			if(v <= vl)//当前未超速 
			{
				if(a <= 0)//不加速 
				{
					continue; 
				}
				if((l*2*a) < (vl*vl-v*v))continue;//全程不超速 除爆了 
				double el = 1.*(vl*vl-v*v)/2/(a);
				int ei = (int)(el+1);//向上取整 且恰好时不算 
				if(ei+d > l)continue;//全程不超速 
				cl[i] = ei+d;cr[i] = l;//超速区间[]
			}
			else//已超速 
			{
				cl[i] = d;
				if(a >= 0)//全程超速 
				{
					cr[i] = l;
					continue;
				}
				if((-1*l*2*a) < (v*v-vl*vl))// 除爆了
				{
					cr[i] = l;continue;
				}
				double el = -1.*(v*v-vl*vl)/2/a;
				assert(el >= 0);
				int ei = (int)(el-Ex);//向下取整 且恰好时不算 
				cr[i] = d+ei;
				assert(cr[i] < l);
//				abort(); 
			}
		}
		sort(w+1,w+n+1,cmp);
		beg = 1;//有效区间开始位置 
		while(cr[w[beg]] == -1)beg++; 
//		for(int i = beg;i <= n;i++)
//		{
//			printf("%d %d\n",cl[w[i]],cr[w[i]]);
//		}
		for(int i = 1;i <= m;i++)
		{
			scanf("%lld",p+i);
		}
		sort(p+1,p+m+1);
		tac = beg;//当前测到了d[tac] 
		cnt = 0;//测出了cnt辆车 
		for(int i = 1;(i <= m) && (tac <= n);i++,tac++)
		{
			if(cl[w[tac]] > p[i])//p[i]太小,检测不到tac 
			{
				tac--;continue; 
			}
			if((cl[w[tac]] <= p[i]) && cr[w[tac]] >= p[i])//检测到了 
			{
//				printf("%d:%d %d %d\n",tac,cl[w[tac]],p[i],cr[w[tac]]);
				vis[w[tac]] = 1;
				cnt++;i--;continue;
			}
			if(cr[w[tac]] < p[i])
			{
				i--;continue; 
			}
		}
		printf("%lld ",cnt);
		//只保留被检测到的区间 
		for(int i = beg;i <= n;i++)
		{
			if(vis[w[i]])//有
			{
//				printf("%d\n",i);
				continue;
			}
			cl[w[i]] = cr[w[i]] = -1;
		}
		sort(w+beg,w+n+1,cmp);
		while(cr[w[beg]] == -1)beg++; 
		
//		for(int i = beg;i <= n;i++)
//		{
//			printf("%d %d\n",cl[w[i]],cr[w[i]]);
//		}
		tac = beg;ans = 0;//最少保留个数 
		for(int i = 1;(i <= m) && (tac <= n);i++)
		{
			if(p[i] <= cr[w[tac]])
			{
				continue;
			}
			ans++;
			int ac = i-1;
//			printf("%d %d\n",ac,p[ac]);
			while((tac <= n) && (cl[w[tac]] <= p[ac]))tac++;
//			for()
//			{
//				if(cl[w[tac]] <= p[ac])
//				{
//					tac++;
//					continue;
//			}
//			}
		}
		if(tac <= n)ans++;//最后一个测速器需要
		printf("%lld\n",m-ans); 
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}

大佬给个小规模数据也行doge

2024/11/8 09:22
加载中...