Description

Botanist Hazel visited a special exhibition at the Singapore Botanic Gardens. In this exhibition, there are $n$ plants with pairwise distinct heights, arranged in a circle. The plants are numbered clockwise from $0$ to $n-1$, and plant $n-1$ is adjacent to plant $0$.

For each plant $i\ (0 \le i \le n-1)$, Hazel compares it with the next $k-1$ plants in the clockwise direction, and records a value $r[i]$, which indicates how many of those $k-1$ plants are taller than plant $i$. Therefore, each value $r[i]$ is determined by the relative heights within some consecutive block of $k$ plants.

For example, suppose $n=5$, $k=3$, and $i=3$. The next $k-1=2$ plants clockwise from plant $3$ are plants $4$ and $0$. If plant $4$ is taller than plant $3$, and plant $0$ is shorter than plant $3$, then Hazel records $r[3]=1$.

You may assume that all the values $r[i]$ recorded by Hazel are correct. That is, there exists at least one set of pairwise distinct heights that matches Hazel’s recorded values.

In this problem, you need to compare the heights of $q$ pairs of plants. Since you did not get to visit the exhibition, the only information you have is Hazel’s notebook, which contains $k$ and the sequence $r[0],\ldots, r[n-1]$.

For each pair of plants $x$ and $y$ to be compared (with $x \ne y$), determine which of the following cases applies:

• Plant $x$ is definitely taller than plant $y$: for any set of pairwise distinct heights $h[0],\ldots,h[n-1]$ that matches array $r$, we have $h[x] > h[y]$.
• Plant $x$ is definitely shorter than plant $y$: for any set of pairwise distinct heights $h[0],\ldots,h[n-1]$ that matches array $r$, we have $h[x] < h[y]$.
• The comparison is inconclusive: neither of the above two cases holds.

Implementation Details

You are required to implement the following functions:

void init(int k, std::vector<int> r)

• $k$: the number of consecutive plants that determine each value $r[i]$.
• $r$: an array of size $n$, where $r[i]$ is the number of plants among the next $k-1$ plants clockwise from plant $i$ that are taller than it.
• This function is called exactly once, before any call to compare_plants.

int compare_plants(int x, int y)

• $x,y$: the indices of the plants to be compared.
• This function should return:
  • $1$, if plant $x$ is definitely taller than plant $y$,
  • $-1$, if plant $x$ is definitely shorter than plant $y$,
  • $0$, if the comparison is inconclusive.
• This function is called exactly $q$ times.

Hint

Sample Explanation

Example 1

Consider the following call:

init(3, [0, 1, 1, 2])

Suppose the grader calls compare_plants(0, 2). From $r[0]=0$, we can conclude that plant $2$ is not taller than plant $0$, so this call should return $1$.

Suppose the grader then calls compare_plants(1, 2). Since for every set of plant heights satisfying the above conditions, plant $1$ is shorter than plant $2$, this call should return $-1$.

Example 2

Consider the following call:

init(2, [0, 1, 0, 1])

Suppose the grader calls compare_plants(0, 3). From $r[3]=1$, we can conclude that plant $0$ is taller than plant $3$, so this call should return $1$.

Suppose the grader then calls compare_plants(1, 3). Two height assignments $[3,1,4,2]$ and $[3,2,4,1]$ both match Hazel’s observations. Since in the first case plant $1$ is shorter than plant $3$, while in the second case it is taller than plant $3$, this call should return $0$.

Constraints

• $2\le k\le n\le 200\ 000$.
• $1\le q\le 200\ 000$.
• $0 \le r[i]\le k-1$ (for all $0 \le i \le n-1$).
• $0\le x<y\le n-1$.
• There exists one or more sets of pairwise distinct heights that match the array $r$.

Subtasks

1. (5 points) $k=2$.
2. (14 points) $n \le 5000, 2 \cdot k > n$.
3. (13 points) $2 \cdot k > n$.
4. (17 points) The correct answer to each compare_plants call is $1$ or $-1$.
5. (11 points) $n\le 300, q\le \frac{n\cdot (n-1)}{2}$.
6. (15 points) In each compare_plants call, $x=0$.
7. (25 points) No additional constraints.

Example Grader

The example grader reads the input in the following format:

Line $1$: $n\ k\ q$
Line $2$: $r[0]\ r[1]\ \cdots\ r[n-1]$
Line $3+i\ (0\le i\le q-1)$: $x\ y$, representing the parameters of the $i$-th call to compare_plants

The example grader prints your answers in the following format:

Line $1+i\ (0\le i\le q-1)$: the return value of the $i$-th call to compare_plants

Translated by ChatGPT 5