Comparing Plants (plants)

Hazel the botanist visited a special exhibition in the Singapore Botanical Gardens. In this exhibition, n plants of distinct heights are placed in a circle. These plants are labelled from 0 to n − 1 in clockwise order, with plant n − 1 beside plant 0.

For each plant i (0 ≤ i < n − 1), Hazel compared plant i to each of the next k − 1 plants in clockwise order, and wrote down the number r[i] denoting how many of these k − 1 plants are taller than plant i. Thus, each value r[i] depends on the relative heights of some k consecutive plants.

For example, suppose n = 5, k = 3 and i = 3. The next k − 1 = 2 plants in clockwise order from plant i = 3 would be plant 4 and plant 0. If plant 4 was taller than plant 3 and plant 0 was shorter than plant 3, Hazel would write down r[3] = 1.

You may assume that Hazel recorded the values r[i] correctly. Thus, there is at least one configuration of distinct heights of plants consistent with these values.

You were asked to compare the heights of pairs of plants. Sadly, you do not have access to the exhibition. Your only source of information is Hazel's notebook with the value k and the sequence of values r[0], . . . , r[n − 1].

For each pair of different plants x and y that need to be compared, determine which of the three following situations occurs:

• Plant x is definitely taller than plant y: in any configuration of distinct heights h[0], . . . , h[n − 1] consistent with the array r we have h[x] > h[y].
• Plant x is definitely shorter than plant y: in any configuration of distinct heights h[0], . . . , h[n − 1] consistent with the array r we have h[x] < h[y].
• The comparison is inconclusive: neither of the previous two cases applies.

Implementation details

You should implement the following procedures:

void init(int k, int[] r)

• k: the number of consecutive plants whose heights determine each individual value r[i].
• r: an array of size n, where r[i] is the number of plants taller than plant i among the next k − 1 plants in clockwise order.
• This procedure is called exactly once, before any calls to compare_plants.

int compare_plants(int x, int y)

• x, y: labels of the plants to be compared.
• This procedure 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 procedure is called exactly q times.

Examples

Example 1

Consider the following call:

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

Let's say the grader calls compare_plants(0, 2). Since r[0] = 0 we can immediately infer that plant 2 is not taller than plant 0. Therefore, the call should return 1.

Let's say the grader calls compare_plants(1, 2) next. For all possible configurations of heights that fit the constraints above, plant 1 is shorter than plant 2. Therefore, the call should return -1.

Example 2

Consider the following call:

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

Let's say the grader calls compare_plants(0, 3). Since r[3] = 1, we know that plant 0 is taller than plant 3. Therefore, the call should return 1.

Let's say the grader calls compare_plants(1, 3) next. Two configurations of heights [3, 1, 4, 2] and [3, 2, 4, 1] are both consistent with Hazel's measurements. Since plant 1 is shorter than plant 3 in one configuration and taller than plant 3 in the other, 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 configurations of distinct heights of plants consistent with the array $r$.

Sample grader

The sample grader reads the input in the following format:

• line 1: n k q
• line 2: r[0] r[1] ... r[n-1]
• line 3 + i (0 ≤ i ≤ q − 1): x y for the i-th call to compare_plants

The sample grader prints your answers in the following format:

• line 1 + i (0 ≤ i ≤ q − 1): return value of the i-th call to compare_plants.

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Comparing Plants)

(plants)

Hazel the botanist visited a special exhibition in the Singapore Botanical Gardens. In this exhibition, n plants of distinct heights are placed in a circle. These plants are labelled from 0 to n − 1 in clockwise order, with plant n − 1 beside plant 0.

For each plant i (0 ≤ i < n − 1), Hazel compared plant i to each of the next k − 1 plants in clockwise order, and wrote down the number r[i] denoting how many of these k − 1 plants are taller than plant i. Thus, each value r[i] depends on the relative heights of some k consecutive plants.

For example, suppose n = 5, k = 3 and i = 3. The next k − 1 = 2 plants in clockwise order from plant i = 3 would be plant 4 and plant 0. If plant 4 was taller than plant 3 and plant 0 was shorter than plant 3, Hazel would write down r[3] = 1.

You may assume that Hazel recorded the values r[i] correctly. Thus, there is at least one configuration of distinct heights of plants consistent with these values.

You were asked to compare the heights of pairs of plants. Sadly, you do not have access to the exhibition. Your only source of information is Hazel's notebook with the value k and the sequence of values r[0], . . . , r[n − 1].

For each pair of different plants x and y that need to be compared, determine which of the three following situations occurs:

• Plant x is definitely taller than plant y: in any configuration of distinct heights h[0], . . . , h[n − 1] consistent with the array r we have h[x] > h[y].
• Plant x is definitely shorter than plant y: in any configuration of distinct heights h[0], . . . , h[n − 1] consistent with the array r we have h[x] < h[y].
• The comparison is inconclusive: neither of the previous two cases applies.

Implementation details

You should implement the following procedures:

void init(int k, int[] r)

• k: the number of consecutive plants whose heights determine each individual value r[i].
• r: an array of size n, where r[i] is the number of plants taller than plant i among the next k − 1 plants in clockwise order.
• This procedure is called exactly once, before any calls to compare_plants.

int compare_plants(int x, int y)

• x, y: labels of the plants to be compared.
• This procedure 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 procedure is called exactly q times.

Examples

Example 1

Consider the following call:

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

Let's say the grader calls compare_plants(0, 2). Since r[0] = 0 we can immediately infer that plant 2 is not taller than plant 0. Therefore, the call should return 1.

Let's say the grader calls compare_plants(1, 2) next. For all possible configurations of heights that fit the constraints above, plant 1 is shorter than plant 2. Therefore, the call should return -1.

Example 2

Consider the following call:

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

Let's say the grader calls compare_plants(0, 3). Since r[3] = 1, we know that plant 0 is taller than plant 3. Therefore, the call should return 1.

Let's say the grader calls compare_plants(1, 3) next. Two configurations of heights [3, 1, 4, 2] and [3, 2, 4, 1] are both consistent with Hazel's measurements. Since plant 1 is shorter than plant 3 in one configuration and taller than plant 3 in the other, 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 configurations of distinct heights of plants consistent with the array $r$.

Sample grader

The sample grader reads the input in the following format:

• line 1: n k q
• line 2: r[0] r[1] ... r[n-1]
• line 3 + i (0 ≤ i ≤ q − 1): x y for the i-th call to compare_plants

The sample grader prints your answers in the following format:

• line 1 + i (0 ≤ i ≤ q − 1): return value of the i-th call to compare_plants.

Execution limits

Your solution will have 4.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "plants.h"

void init(int k, std::vector<int> r) {
    return;
}

int compare_plants(int x, int y) {
    return 0;
}

参考函数签名

#include "plants.h"

void init(int k, std::vector<int> r) {
    return;
}

int compare_plants(int x, int y) {
    return 0;
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "plants.h"

void init(int k, std::vector<int> r) {
return;
}

int compare_plants(int x, int y) {
return 0;
}