BZOJ5194: [Usaco2018 Feb]Snow Boots（排序&set）

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=100010;
int s[maxn],d[maxn],ans[maxn],p[maxn];
bool cmp(int w,int v){ return s[w]<s[v];}
multiset<int>Len,Point;
multiset<int>::iterator it1,it2;
struct in{
    int s,id;
    friend bool operator<(in w,in v){ return w.s<v.s;}
}f[maxn];
int main()
{
    int N,B; scanf("%d%d",&N,&B);
    rep(i,1,N) scanf("%d",&f[i].s),f[i].id=i;
    sort(f+1,f+N+1);
    rep(i,1,B) scanf("%d%d",&s[i],&d[i]);
    rep(i,1,B) p[i]=i;
    sort(p+1,p+B+1,cmp);
    int head=0;
    Len.insert(N-1);  Point.insert(1); Point.insert(N);
    rep(i,1,B){
        int now=p[i];
        while(head<N&&s[now]>=f[head+1].s){
            head++; if(f[head].id==1||f[head].id==N) continue;
            it1=Point.lower_bound(f[head].id); it1--;
            it2=Point.upper_bound(f[head].id);
            Len.insert(*it2-f[head].id); Len.insert(f[head].id-*it1);
            Point.insert(f[head].id);Len.erase(Len.find(*it2-*it1));
        }
        if((*(--Len.end()))<=d[now]) ans[now]=1;

    }
    rep(i,1,B) printf("%d\n",ans[i]);
    return 0;
}