萌新求助..不知道为什么WA了(QAQ)
查看原帖
萌新求助..不知道为什么WA了(QAQ)
287539
勇敢的菜鸡楼主2020/7/15 14:33
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;
typedef long long LL;
struct Cow
{
  LL x;LL h;	
}a[maxn];
LL L[maxn],R[maxn];
LL stack[maxn];
LL N,D;
bool cmp(Cow k,Cow l)
{
	return k.x<l.x;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  freopen("P3088_2.in","r",stdin);
  cin>>N>>D;
  for(LL i=1;i<=N;i++)
  {
  	cin>>a[i].x>>a[i].h;
  }
  sort(a+1,a+1+N,cmp);
//  cout<<endl;
//  for(LL i=1;i<=N;i++)
//  {
//  	cout<<a[i].x<<' '<<a[i].h<<endl;
//  }
//  cout<<endl;
  LL top=0;
  for(LL i=1;i<=N;i++)
  {
  	 while(top!=0&&a[stack[top]].h*2<=a[i].h) R[stack[top]]=i,top--;
	 stack[++top]=i;
  }
  for(LL i=1;i<=top;i++) R[stack[i]]=3000000000;
  
  top=0;
  for(LL i=N;i>=1;i--)
  {
  	while(top!=0&&a[stack[top]].h*2<=a[i].h) L[stack[top]]=i,top--;
  	stack[++top]=i;
  }
  for(LL i=1;i<=top;i++) L[stack[i]]=-3000000000;
  LL ans=0;
  
//  for(LL i=1;i<=N;i++)
//	{
//	   cout<<"R["<<i<<"]="<<R[i]<<"and"<<"L["<<i<<"]="<<L[i]<<endl;	
//	}  
  for(LL i=1;i<=N;i++)
  {
  	if(R[i]-L[i]<=2*D) ans++;  	
  }
  cout<<ans<<endl;
return 0;
}

2020/7/15 14:33
加载中...