蒟蒻的小窝

蒟蒻的小窝

题解 P3088 【[USACO13NOV]Crowded Cows S】

posted on 2020-08-15 19:57:04 | under 题解 |

这题我的想法是 $RMQ$ 。 $RMQ$ 刷区间内的最大值嘛,然后对于每个点,只要左边的区间的最大值大于自身,那就把左边区间的左边界往右拱一拱,拱的过程用二分 $\log_2(n)$ 的时效来实现,右边的区间做法和左边一样啊,区间越小越好嘛,然后如果左区间的左端点到自身的距离小于等于 $k$ ,右区间的右端点到自身的距离也小于 $k$, $ans$ 就加加,最后输出 $ans$ 就ok了。

Code:

#include<bits/stdc++.h>
using namespace std;
struct ZS{
    int x,h;
    bool operator <(const ZS b)const{return x<b.x;}
}a[50005];
int n,d,ans;
int b[50005][20];
int find(int x){
    int L=1,R=x,mid,cnt=1<<30;
    while(L<=R){
        mid=(R-L>>1)+L;
        if(a[mid].x>=a[x].x-d)cnt=min(cnt,mid),R=mid-1;
        else L=mid+1;
    }
    return cnt;
}
int find_(int x){
    int L=x,R=n,mid,cnt=0;
    while(L<=R){
        mid=(R-L>>1)+L;
        if(a[mid].x<=a[x].x+d)cnt=max(cnt,mid),L=mid+1;
        else R=mid-1;
    }
    return cnt;
}
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}
int main(){
    n=read();d=read();
    for(int i=1;i<=n;i++)a[i].x=read(),a[i].h=read();
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)b[i][0]=a[i].h;
    for(int j=1;j<=18;j++)
        for(int i=1;i<=n;i++)if(i+(1<<j-1)<=n)b[i][j]=max(b[i][j-1],b[i+(1<<j-1)][j-1]);
    for(int i=1;i<=n;i++){
        int l=find(i),r=find_(i);
        int x=log2(i-l+1),y=log2(r-i+1);
        int L=max(b[l][x],b[i-(1<<x)+1][x]),R=max(b[i][y],b[r-(1<<y)+1][y]);
        if(L>=2*a[i].h&&R>=2*a[i].h)ans++;
    }
    printf("%d\n",ans);
    return 0;
}