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

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

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

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

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

16A68F47291454A0D46AF2C75AC595D5.jpg

在田径运动中,选手身后的棱台就是发令喇叭

时辰一到,所有开着的发令喇叭会同时发出起跑信号(下文简称发炮)。如果 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

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

数据范围与提示

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

子任务 #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