LibreOJ

2849 「ROI 2018 Day 2」机器人马拉松

内存限制：256 MB 时间限制：1000 ms

题目描述

译自 ROI 2018 Day2 T3. Робомарафон (Robomarathon)

有 $N$ 名机器人选手参加马拉松，选手的编号分别为 $1\ldots N$。跑道包含 $N$ 条分道，编号分别为 $1\ldots N$。每位选手占据一条分道，$i$ 号选手（简称 $i$ 号）占据编号为 $i$ 的分道（简称 $i$ 道）。每条分道从起点到终点的路程均相同。已知 $i$ 号跑完全程需要 $a_i$ 秒。

每条分道的起始点有一个发令喇叭，不过不是播声音的。裁判皮了一下，把有些分道上的发令喇叭关掉了。

时辰一到，所有开着的发令喇叭会同时发出起跑信号（下文简称发炮）。如果 $i$ 道上发炮，$i$ 号会立即起跑。

发令信号的传递速度为每秒钟 1 道。举个例子，如果有且只有四道上发炮，那么一秒后三号和五号会收到信号并立即起跑；两秒后二号和六号会收到信号并立即起跑。假设 $i$ 号在第 $x_i$ 秒起跑，则他会在第 $f_i =$ $a_i + x_i$ 秒冲线。

我们按照冲线顺序给选手排名。比如，如果 $n=3,$ $f_1=$ $f_2=$ $4,$ $f_3=$ $5,$ 那么一号和二号并列第一，三号屈居第三。

可见，选手的排名取决于发令喇叭的开关状态。请求出每位选手的最好名次或最差名次。

输入格式

第一行：$n,p,$ $p=1$ 或 $2,$ $1$ 表示你需要求出最好名次，$2$ 表示你需要求出最差名次。
第二行：$a_1\ldots a_n$

样例 1

样例 2

数据范围与提示

对于所有数据，$0<a_i\le 10^9$。

子任务 # 分值 测试点数量 $n⩽$ $p=$ 计分方式
1 10 $20$ $1$ min
2  10  $20$ $2$ min
3 30  30  $4\times 10^5$ $1$ sum
4 50  50  $4\times 10^5$ $2$ sum

子任务 #3 中，各测试点的大小：

测试点 $n=$ 测试点 $n=$ 测试点 $n=$ 测试点 $n=$ 测试点 $n=$
1 $ 100$ 7 $1.5×10^4$ 13 $7×10^4$ 19 $1.3×10^5$ 25 $2×10^5$
2 $ 500$ 8 $2×10^4$ 14 $8×10^4$ 20 $1.4×10^5$ 26 $2.4×10^5$
3 $1000$ 9 $3×10^4$ 15 $9×10^4$ 21 $1.5×10^5$ 27 $2.8×10^5$
4 $2500$ 10 $4×10^4$ 16 $99999$ 22 $1.6×10^5$ 28 $3.2×10^5$
5 $4999$ 11 $5×10^4$ 17 $1.1×10^5$ 23 $1.7×10^5$ 29 $3.6×10^5$
6 $10^4$ 12 $6×10^4$ 18 $1.2×10^5$ 24 $1.8×10^5$ 30 $4×10^5$

子任务 #4 中，各测试点的大小：

测试点 $n=$ 测试点 $n=$ 测试点 $n=$ 测试点 $n=$ 测试点 $n=$
1 $100$ 11 $2500$ 21 $3\times 10^4$ 31 $109999$ 41 $2.2\times 10^5$
2 $200$ 12 $3000$ 22 $3.5\times 10^4$ 32 $1.2\times 10^5$ 42 $2.4\times 10^5$
3 $300$ 13 $4000$ 23 $4\times 10^4$ 33 $1.3\times 10^5$ 43 $2.6\times 10^5$
4 $400$ 14 $4999$ 24 $4.5\times 10^4$ 34 $1.4\times 10^5$ 44 $2.8\times 10^5$
5 $500$ 15 $7500$ 25 $5\times 10^4$ 35 $1.5\times 10^5$ 45 $3\times 10^5$
6 $750$ 16 $10^4$ 26 $6\times 10^4$ 36 $1.6\times 10^5$ 46 $3.2\times 10^5$
7 $1000$ 17 $1.25\times 10^4$ 27 $7\times 10^4$ 37 $1.7\times 10^5$ 47 $3.4\times 10^5$
8 $1250$ 18 $1.5\times 10^4$ 28 $8\times 10^4$ 38 $1.8\times 10^5$ 48 $3.6\times 10^5$
9 $1500$ 19 $2\times 10^4$ 29 $9\times 10^4$ 39 $1.9\times 10^5$ 49 $3.8\times 10^5$
10 $1999$ 20 $2.5\times 10^4$ 30 $99999$ 40 $2\times 10^5$ 50 $4\times 10^5$

<!--Russia Team Open, High School Programming Contest 2018: BCFJK>

样例

样例输入 1

5 1
8 5 5 7 7

样例输出 1

3
1
1
2
1

样例输入 2

5 2
8 5 5 7 7

样例输出 2

5
3
2
4
5