Snow Boots

题目描述

农场里到了冬天，也就意味着下雪！从农舍到牛棚的路上有 $N$ 块地砖，方便起见编号为 $1 \dots N$，其中第 $i$ 块地砖上覆盖着 $f_i$ 英尺深的积雪。 在农舍的地窖里，农夫约翰有 $B$ 双靴子，编号为 $1 \dots B$。有些靴子更耐用，有些靴子更灵活。具体来说，第 $i$ 双靴子允许 FJ 踩在最深为 $s_i$ 英尺的积雪上，并且每一步最多可以向前走 $d_i$。 农夫约翰从地砖 $1$ 出发，必须到达地砖 $N$ 来叫醒奶牛。地砖 $1$ 被农舍屋顶遮蔽，地砖 $N$ 被牛棚屋顶遮蔽，因此这两块地砖都没有积雪。请帮助农夫约翰判断哪些靴子能让他完成这段路程。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $B$（$1 \leq N,B \leq 10^5$）。 第二行包含 $N$ 个用空格分隔的整数；第 $i$ 个整数为 $f_i$，表示第 $i$ 块地砖上的积雪深度（$0 \leq f_i \leq 10^9$）。保证 $f_1 = f_N = 0$。 接下来的 $B$ 行每行包含两个用空格分隔的整数。第 $i+2$ 行的第一个整数为 $s_i$，表示第 $i$ 双靴子可踩踏的最大积雪深度；第二个整数为 $d_i$，表示第 $i$ 双靴子的最大步长。 保证 $0 \leq s_i \leq 10^9$ 且 $1 \leq d_i \leq N-1$。

输出格式

输出应包含 $B$ 行。第 $i$ 行输出一个整数：如果农夫约翰穿第 $i$ 双靴子能够从地砖 $1$ 走到地砖 $N$，则输出 $1$；否则输出 $0$。

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

0
1
1
0
1
1
1

提示

题目鸣谢：Dhruv Rohatgi

标签: USACO|2018|Gold

来源

USACO|2018|Gold