BZOJ5194: [Usaco2018 Feb]Snow Boots（排序&set）（可线段树优化）

5194: [Usaco2018 Feb]Snow Boots

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 102 Solved: 79
[Submit][Status][Discuss]

Description

到冬天了，这意味着下雪了！从农舍到牛棚的路上有N块地砖，方便起见编号为1…N，第i块地砖上积了fi英尺的雪

。在Farmer John的农舍的地窖中，总共有B双靴子，编号为1…B。其中某些比另一些结实，某些比另一些轻便。具

体地说，第i双靴子能够让FJ在至多si英尺深的积雪中行走，能够让FJ每步至多前进di。Farmer John从1号地砖出

发，他必须到达N号地砖才能叫醒奶牛们。1号地砖在农舍的屋檐下，N号地砖在牛棚的屋檐下，所以这两块地砖都

没有积雪。帮助Farmer John求出哪些靴子可以帮助他走完这段艰辛的路程。

Input

第一行包含两个空格分隔的整数N和B（1≤N,B≤10^5）。

第二行包含N个空格分隔的整数；第i个整数为fi，即i号地砖的积雪深度（0≤fi≤10^9）。输入保证f1=fN=0

下面B行，每行包含两个空格分隔的整数。第i+2行的第一个数为si，表示第i双靴子能够承受的最大积雪深度。

第i+2行的第二个数为di，表示第i双靴子的最大步长。输入保证0≤si≤10^9以及1≤di≤N-1

Output

输出包含N行

第i行包含一个整数：如果Farmer John能够穿着第i双靴子从1号地砖走到N号地砖，为1，否则为0

Sample Input

8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

Sample Output

0
1
1
0
1
1
1

HINT

Source

Gold

思路：一眼就想到这个算法了：鞋子按照能到达的深度排序，地砖也是。因为我们鞋子能踩的深度越大，那么相邻的地砖越近，如果当前最远的相邻地砖在走的范围内，说明ok。我们然后每次把可以踩的地砖加进去，然后set维护前驱后继，再维护一个set是相邻地砖距离。

虽然AC了，写完发现自己时间有点久，看了一下，其他的做法也是差不多，只是用线段树来维护的，把可以踩的地砖看成1，否则为0，那么就是线段树查询最大连续0的个数的常规操作。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

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,,N) scanf("%d",&f[i].s),f[i].id=i;

    sort(f+,f+N+);

    rep(i,,B) scanf("%d%d",&s[i],&d[i]);

    rep(i,,B) p[i]=i;

    sort(p+,p+B+,cmp);

    int head=;

    Len.insert(N-);  Point.insert(); Point.insert(N);

    rep(i,,B){

        int now=p[i];

        while(head<N&&s[now]>=f[head+].s){

            head++; if(f[head].id==||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]=;

    }

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

    return ;

}

秒客网