P9292 [ROI 2018] Robomarathon

Translated from [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T3. [Робомарафон](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf) ([Robomarathon](https://codeforces.com/gym/102154/problem/D)).

There are $N$ robot runners in a marathon, numbered $1 \ldots N$. The track has $N$ lanes, also numbered $1 \ldots N$. Each runner occupies one lane: runner $i$ (or simply $i$) is in lane $i$ (or simply lane $i$). All lanes have the same distance from start to finish. It is known that runner $i$ needs $a_i$ seconds to finish the whole distance. At the start of each lane there is a starting horn, but it does not play sound. The referee played a prank and turned off the starting horns on some lanes. When the time comes, all starting horns that are on will send the start signal at the same time (called “firing” below). If lane $i$ fires, runner $i$ will start immediately. The start signal propagates at a speed of $1$ lane per second. For example, if only lane $4$ fires, then after one second runners $3$ and $5$ will receive the signal and start immediately; after two seconds runners $2$ and $6$ will receive the signal and start immediately. Suppose runner $i$ starts at second $x_i$, then they will finish at second $f_i = a_i + x_i$. We rank runners by their finishing order. For example, if $n=3$, $f_1 = f_2 = 4$, and $f_3 = 5$, then runner $1$ and runner $2$ are tied for first place, and runner $3$ is third. As you can see, the ranking depends on which starting horns are turned on. Please find, for each runner, their best possible rank or their worst possible rank.

The first line contains $n$, $p$. The next line contains $n$ numbers, representing $a_1, a_2 \ldots a_n$.

If $p = 1$, output the best possible rank. If $p = 2$, output the worst possible rank.

For all testdata, $1 \leq n \leq 4 \times 10^5$, $0 \leq a_i \leq 10^9$. | Subtask ID | $n$ | $p$ | | :-----------: | :-----------: | :-----------: | | $1$ | $1 \leq n \leq 20$ | $p = 1$ | | $2$ | $1 \leq n \leq 20$ | $p = 2$ | | $3$ | $1 \leq n \leq 4 \times 10^5$ | $p = 1$ | | $4$ | $1 \leq n \leq 4 \times 10^5$ | $p = 2$ | In Subtasks $3$ and $4$, each test point is worth $1$ point, and the total score is the sum. Translated by ChatGPT 5