[ROI 2018] Robomarathon

Luogu

IDLGP9292

Time1000ms

Memory512MB

DifficultyP5

树形数据结构2018线段树树状数组扫描线ROI（俄罗斯）

有 $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$, 那么一号和二号并列第一，三号屈居第三。可见，选手的排名取决于发令喇叭的开关状态。请求出每位选手的最好名次或最差名次。 ## Input 第一行：$n$，$p$。接下来一行 $n$ 个数，表示 $a_1$，$a_2 \ldots a_n$。 ## Output 如果 $p=1$，输出最好名次。如果 $p=2$，输出最差名次。 [samples] ## Background 译自 [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))。 ## Note 对于所有数据，$1 \leq n \leq 4 \times 10^5$，$0\leq a_i \leq 10^9$。 | 子任务编号 | $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$ | 其中，Subtask 3 和 4 内的每个测试点 1 分，加和计算。

Samples

Input #1

5 1
8 5 5 7 7

Output #1

Input #2

5 2
8 5 5 7 7

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2018] Robomarathon",
    "description": {
      "content": "有 $N$ 名机器人选手参加马拉松，选手的编号分别为 $1\\ldots N$。跑道包含 $N$ 条分道，编号分别为 $1\\ldots N$。每位选手占据一条分道，$i$ 号选手（简称 $i$ 号）占据编号为 $i$ 的分道（简称 $i$ 道）。每条分道从起点到终点的路程均相同。已知 $i$ 号跑完全程需要 $a_i$ 秒。 每条分道的起始点有一个发令喇叭，不过不是播声音的。裁判皮了一下，把有些分",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9292"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $N$ 名机器人选手参加马拉松，选手的编号分别为 $1\\ldots N$。跑道包含 $N$ 条分道，编号分别为 $1\\ldots N$。每位选手占据一条分道，$i$ 号选手（简称 $i$ 号）占据编号为 $i$ 的分道（简称 $i$ 道）。每条分道从起点到终点的路程均相同。已知 $i$ 号跑完全程需要 $a_i$ 秒。\n\n每条分道的起始点有一个发令喇叭，不过不是播声音的。裁判皮了一下，把有些分...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments