关于为什么没能达到最后AC+1,却WA了1个点(QAQ)
查看原帖
关于为什么没能达到最后AC+1,却WA了1个点(QAQ)
68960
M_and_P_楼主2020/10/29 23:19

代码是单调队列手打模拟,却浑然不知为何WA*1,麻烦各位 dalao指教一下,连模板题都卡的蒟蒻万分感谢!!

上WA*1的代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=50005;
struct node{
	ll x,h;
}a[N];
ll q[N];
ll vis[N],head,tail,n,d;
bool cmp(node x,node y)
{
	return x.x<y.x;
}
int main()
{
	scanf("%lld%lld",&n,&d);
	for (ll i=1;i<=n;i++)
		scanf("%lld%lld",&a[i].x,&a[i].h);
	stable_sort(a+1,a+n+1,cmp);
	head=1;tail=0;
	//1 to n to solve left
	for (ll i=1;i<=n;i++)
	{
		while(head<=tail&&a[q[head]].x-a[i].x>d)head++;
		if (a[q[head]].h>=a[i].h*2)vis[i]++;
		while(head<=tail&&a[i].h>=a[q[tail]].h)tail--;
		q[++tail]=i;
	}
	memset(q,0,sizeof(q));
	head=1,tail=0;
	//n to 1 to solve right
	for (ll i=n;i>=1;i--)
	{
		while(head<=tail&&a[q[head]].x-a[i].x>d)head++;
		if (a[q[head]].h>=a[i].h*2)vis[i]++;
		while(head<=tail&&a[i].h>=a[q[tail]].h)tail--;
		q[++tail]=i;
	}
	ll ans=0;
	for (ll i=1;i<=n;i++)
	if (vis[i]==2)ans++;
	printf("%lld",ans);
	return 0;
} 
2020/10/29 23:19
加载中...