19933번 - Comparing 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ドル \leq i \leq 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 $q$ 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], \ldots, 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], \ldots, 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], \ldots, 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.

구현

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.

입력

출력

제한

• 2ドル \leq k \leq n \leq 200\;000$
• 1ドル \leq q \leq 200\;000$
• 0ドル \leq r[i] \leq k - 1$ (for all 0ドル \leq i \leq n - 1$)
• 0ドル \leq x < y \leq n - 1$
• There exists one or more configurations of distinct heightsof plants consistent with the array $r$.

예시 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$.

예시 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ドル$.

서브태스크

힌트

첨부

• plants.zip