5194: [Usaco2018 Feb]Snow Boots

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 81  Solved: 61

[][][]

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

题目链接：

　　　　 

Solution

　　这种题感觉已经是套路了。。。

　　反正就是两种思路。。。　　

　　1.只走小于D的雪堆需要走的最长的一步。。

　　2.最长的一步为不超过S的需要走的最大的雪堆。。

　　这里只写了第1种的。。。第2种应该也能写吧。。

　　先将所有雪堆从小到大排序，鞋子也要排序。。

　　对于某一种鞋子的di，求一下需要多大的si。。。就是求一下能走的雪堆的最大间隔。。

　　每次放入一个新的雪堆只会改变几个间隔大小。。

　　所以只需要用set维护一下集合内的前驱和后驱，然后用两个优先队列维护一下带删除的集合内最大值。。

　　然后就做完了。。。

代码

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            

S;priority_queue

P,Q;void del(int x){ Q.push(x); while(Q.empty()==0&&P.empty()==0&&Q.top()==P.top()){ P.pop();Q.pop(); }}void add(int x){ P.push(x);}int ans[N];int main(){ n=read();m=read(); if(n==1||n==2){ for(int i=1;i<=m;++i){ putchar('1');puts(""); } return 0; } f[1].v=read(); for(int i=2;i

::iterator L,R; int l,r; S.insert(1);S.insert(n+2); for(int i=1,j=1;j<=m;++j){ while(i<=n&&f[i].v<=a[j].s){ R=S.lower_bound(f[i].id); L=R;--L; l=*L;r=*R; del(r-l); add(f[i].id-l); add(r-f[i].id); S.insert(f[i].id); ++i; } if(P.top()<=a[j].d) ans[a[j].id]=1; else ans[a[j].id]=0; } for(int i=1;i<=m;++i) printf("%d\n",ans[i]); return 0;}