单调队列0分球条
查看原帖
单调队列0分球条
1338740
_User114514_楼主2024/7/1 15:55
#include<bits/stdc++.h>
using namespace std;
int n,d,ans;
struct cow{
    int x,h;
    bool l=false,r=false;
}a[50005];
deque<cow> q;
bool cmp(cow kkk,cow che){
    kkk.x<che.x;
}
int main(){
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].h;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.front().x+d<a[i].x)q.pop_front();
        while(!q.empty()&&q.back().h<=a[i].h)q.pop_back();
        q.push_back(a[i]);
        if(q.front().h>=a[i].h*2)a[i].l=1;
    }
    q.clear();
    for(int i=n;i>=1;i--){
        while(!q.empty()&&q.front().x-d>a[i].x)q.pop_front();
        while(!q.empty()&&q.back().h<=a[i].h)q.pop_back();
        q.push_back(a[i]);
        if(q.front().h>=a[i].h*2)a[i].r=1;
    }
    for(int i=1;i<=n;i++)if(a[i].l&&a[i].r)ans++;
    cout<<ans;
    return 0;
}
2024/7/1 15:55
加载中...