~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~
2019寒假集训题
#.Snow Boots S
题面
到冬天了，这意味着下雪了！从农舍到牛棚的路上有$N$块地砖，方便起见编号为$1…N$，第i块地砖上积了$f_i$英尺的雪 。在$Farmer John$的农舍的地窖中，总共有$B$双靴子，编号为$1…B$。其中某些比另一些结实，某些比另一些轻便。具体地说，第i双靴子能够让$FJ$在至多$s_i$英尺深的积雪中行走，能够让$FJ$每步至多前进$d_i$。$Farmer John$从$1$号地砖出发，他必须到达$N$号地砖才能叫醒奶牛们。$1$号地砖在农舍的屋檐下，$N$号地砖在牛棚的屋檐下，所以这两块地砖都没有积雪。帮助$Farmer John$求出哪些靴子可以帮助他走完这段艰辛的路程。
Input
第一行包含两个空格分隔的整数$N$和$B$。
第二行包含$N$个空格分隔的整数；第$i$个整数为$f_i$，即$i$号地砖的积雪深度。
下面$B$行，每行包含两个空格分隔的整数。第$i+2$行的第一个数为$s_i$，表示第$i$双靴子能够承受的最大积雪深度。
第$i+2$行的第二个数为$d_i$，表示第$i$双靴子的最大步长。
Output
输出包含$N$行。第$i行$包含一个整数：如果$FarmerJohn$能够穿着第$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
输入保证$f_1=f_N=0$ ，$0≤s_i≤10^9$。
$1≤d_i≤N-1$，$0≤f_i≤10^9$。
$1≤N,B≤10^5$。
我先弃个坑。
1 |