6duI0X - Online C++ Compiler & Debugging Tool

#include <bits/stdc++.h>

using namespace std;
using ll=long long;
//using int=long long;
int const MAXN=1e5+10;
int const INF=2e9+10;
void open(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
}
pair<int,int> f[MAXN];
pair<pair<int,int>,int> s[MAXN];
bool ans[MAXN];
int N,B;

int main() {
    open();
    cin>>N>>B;
    for(int i=1;i<=N;i++){
        cin>>f[i].first;
        f[i].second=i;
    }

    for(int i=1;i<=B;i++){
        cin>>s[i].first.first>>s[i].first.second;
        s[i].second=i;
    }

    sort(f+1,f+N+1);
    sort(s+1,s+B+1);

    set<int> points;
    multiset<int> dist;
    points.insert(1);points.insert(N);dist.insert(N-1);

    for(int i=1,j=0;i<=B;i++){
        while(j<N && f[j+1].first<=s[i].first.first){
            j++;
            auto right=points.upper_bound(f[j].second);
            auto left=prev(right);

            dist.erase(dist.find(*right-*left));
            dist.insert(f[j].second-*left);
            dist.insert(*right-f[j].second);
            points.insert(f[j].second);
        }
        bool flag=0;
        int max_dist=*dist.rbegin();

        if(max_dist<=s[i].first.second) flag=1;
        ans[s[i].second]=flag;
    }

    for(int i=1;i<=B;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}