代码是单调队列手打模拟,却浑然不知为何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;
}