Jumping Around
Contest: Educational Codeforces Round 111 (Rated for Div. 2)
Difficulty rating: 2700
Tags: binary search, data structures, divide and conquer, dp, dsu, graphs, shortest paths

There is an infinite pond that can be represented with a number line. There are $$$n$$$ rocks in the pond, numbered from $$$1$$$ to $$$n$$$. The $$$i$$$-th rock is located at an integer coordinate $$$a_i$$$. The coordinates of the rocks are pairwise distinct. The rocks are numbered in the increasing order of the coordinate, so $$$a_1 < a_2 < \dots < a_n$$$.

A robot frog sits on the rock number $$$s$$$. The frog is programmable. It has a base jumping distance parameter $$$d$$$. There also is a setting for the jumping distance range. If the jumping distance range is set to some integer $$$k$$$, then the frog can jump from some rock to any rock at a distance from $$$d - k$$$ to $$$d + k$$$ inclusive in any direction. The distance between two rocks is an absolute difference between their coordinates.

You are assigned a task to implement a feature for the frog. Given two integers $$$i$$$ and $$$k$$$ determine if the frog can reach a rock number $$$i$$$ from a rock number $$$s$$$ performing a sequence of jumps with the jumping distance range set to $$$k$$$. The sequence can be arbitrarily long or empty.

You will be given $$$q$$$ testcases for that feature, the $$$j$$$-th testcase consists of two integers $$$i$$$ and $$$k$$$. Print "Yes" if the $$$i$$$-th rock is reachable and "No" otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", "Yes" and 'YES"' will be recognized as a positive answer).

Input format:
The first line contains four integers $$$n$$$, $$$q$$$, $$$s$$$ and $$$d$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$; $$$1 \le s \le n$$$; $$$1 \le d \le 10^6$$$) — the number of rocks, the number of testcases, the starting rock and the base jumping distance parameter.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the coordinates of the rocks. The coordinates of the rocks are pairwise distinct. The rocks are numbered in the increasing order of distance from the land, so $$$a_1 < a_2 < \dots < a_n$$$.

Each of the next $$$q$$$ lines contains two integers $$$i$$$ and $$$k$$$ ($$$1 \le i \le n$$$; $$$1 \le k \le 10^6$$$) — the parameters to the testcase.

Output format:
For each of the testcases print an answer. If there is a sequence of jumps from a rock number $$$s$$$ to a rock number $$$i$$$ with the jumping distance range set to $$$k$$$, then print "Yes". Otherwise, print "No".

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
Explanation of the first example:

In the first testcase the destination rock is the same as the starting rock, thus no jumps are required to reach it.

In the second testcase the frog can jump any distance in the range $$$[5 - 2; 5 + 2]$$$. Thus, it can reach rock number $$$5$$$ (by jumping $$$7$$$ to the right) and rock number $$$3$$$ (by jumping $$$3$$$ to the left). From rock number $$$3$$$ it can reach rock number $$$2$$$ (by jumping $$$5$$$ to the left). From rock number $$$2$$$ it can reach rock number $$$1$$$ (by jumping $$$4$$$ to the left). However, there is no way to reach rock number $$$7$$$.

In the third testcase the frog can jump any distance in the range $$$[5 - 3; 5 + 3]$$$. Thus, it can reach rock number $$$7$$$ by jumping to rock $$$5$$$ first and to $$$7$$$ afterwards.

The fourth testcase is shown in the explanation for the second testcase.

Example input:
7 4 4 5
1 5 10 13 20 22 28
4 1
7 2
7 3
3 2

Example output:
Yes
No
Yes
Yes

Example input:
10 8 6 11
1 2 4 7 8 9 11 13 19 20
2 13
5 8
8 1
6 15
1 15
2 7
7 6
8 9

Example output:
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes

Editorial:
Notice that increasing $$$k$$$ only increases the range of the jump distances in both directions. So every rock that was reachable with some $$$k$$$, will be reachable with $$$k+1$$$ as well. Thus, let's try to find the smallest possible value of $$$k$$$ to reach each rock.
Let's imagine this problem as a graph one and consider the following algorithm. For every pair of rocks, make an edge of weight equal to the smallest $$$k$$$ required to jump from one to another. For some rocks $$$v$$$ and $$$u$$$ that is $$$w = |d - |a_v - a_u||$$$. How to check the reachability with these edges? Well, if the jump range value is $$$k$$$, then there should exist of path by edges of weight no more than $$$k$$$. So we can start with an empty graph, first add the edges of the smallest weight, then the second smallest, and so on. The first time a pair of vertices becomes reachable from each other is the minimum such weight.
An experienced reader can notice the resemblance with the Kruskal algorithm for finding the minimum spanning tree. After the spanning tree is constructed, the minimum $$$k$$$ is the maximum value on a path between the vertices.
The issue is that Kruskal requires $$$O(n^2 \log n^2)$$$ to construct an MST for a complete graph. Prim can make it $$$O(n^2)$$$, which is still too much. Thus, the solution is to resort to Boruvka.
On each iteration of Boruvka we have to find the smallest weight edge from each component to some other one. We can solve it the following way. Maintain a sorted set of rocks coordinates. The smallest weight edges are the ones that are the closest to $$$d$$$ distance from each rock. So we could query a lower_bound of $$$a_i - d$$$ and $$$a_i + d$$$ on each rock $$$i$$$ to find them. Don't forget to look at the both sides of the lower_bound result.
However, the issue is that we can bump into the rocks from the same component. Thus, let's process components one by one. When processing a component, first remove all its vertices from the set. Then query the edges for each vertex. Then add the vertices back. This way, only the edges to other components will be considered.
That makes it an $$$O(n \log^2 n)$$$ construction, with one log from the number of Boruvka iterations and another $$$n \log n$$$ from finding the edges. That should pass if coded carefully enough, and that is basically the intended solution.
Still, there exists a $$$O(n \log n)$$$ construction. That will require a $$$O(n)$$$ algorithm for finding the edges. So there are four possible edges for each rock $$$i$$$: the closest to $$$a_i - d$$$ from the left, from the right and the same for $$$a_i + d$$$. Let's consider only the first case, the rest will be similar.
The coordinates are sorted beforehand, and we are processing the rocks from left to right. We can maintain a pointer to the latest encountered rock to the left of $$$a_i - d$$$. The issue with it being from the same component is still there. Let's go around it by also storing the second latest encountered rock such that it's from the different component from the actual latest one. This can be updated in the same manner one calculates the second maximum of the array.
Now you just have to do that for all four cases. This two pointers approach makes it $$$O(n)$$$ for each iteration, thus making the construction $$$O(n \log n)$$$.
Since the queries ask for a path from some fixed vertex $$$s$$$ to a certain vertex $$$i$$$, it's the same as calculating the maximum edge on a path from the root of the tree to each vertex. Can be done with a simple dfs. The only thing left is to check if the minimum possible $$$k$$$ is less than or equal to the one provided in the query.
Overall complexity: $$$O(n \log^2 n + q)$$$ or $$$O(n \log n + q)$$$.