← 返回题目列表

AtCoder · s8pc_6_g

G. 奖牌

中文机器翻译题面 查看原题

最高分数:1200 点

问题陈述

2212年,竞技性编程比现在更加出名,国际信息学奥林匹克(IOI)是世界上最著名的竞赛之一。

今年, N 参赛者,其ID编号为 1 to N,参加IOI。

比赛举行于 2 天数如下:

  • 天 1:有纸质测试。参赛者 i 得到 A_i 点。可以保证 A_i \neq A_j (1 \leq i < j \leq N).
  • 天 2:有一个实际测试。在此测试中,得分介于 将为每位参赛者授予 1 和 N 。表现最好的选手将获得 N 分,表现第二好的选手将获得 N - 1 分,...,表现最差的参赛者将获得 1 点。

目前,你知道Day-1 所有参与者的分数。但你对Day一无所知-2 结果。
在 IOI 规则中,参与者的 最终成绩 为(纸质考试成绩)+(实践考试成绩)。

的 排名 参赛者的 将确定如下:

  • 基本上,最终分数越高,排名越高。 (注:最高等级为 1,最低等级是 N.)
  • 若出现平局,则在得分相同的选手中随机抽签决定名次。

此外,获得排名的参赛者 1 将获得金牌,获得名次的选手 2 将获得银牌,获得名次的选手 3 将获得铜牌。

他又知道了IOI 2212最终排名的一则信息。该信息以一个整数表示 P (要么 1 or 2).

  • 让 X 为获得金牌的参赛者ID。
  • 让 Y 为获得银牌的参赛者ID。
  • 让 Z 为获得铜牌的参赛者ID。
  • If P = 1, A_X > A_Y > A_Z 满意。
  • If P = 2, A_X > A_Z > A_Y 满意。

有多少种可能的组合 (X, Y, Z) 有吗?

约束

  • N 是介于 5 和 1 \ 000 \ 000 (含)
  • P 是 1 or 2
  • A_i 是介于 1 和 1 \ 000 \ 000 \ 000 (含)
  • 全部 A_i 不同。

子任务和评分

在这个问题中,有 2 子任务如下。

  1. (600分):P = 1
  2. (600分):P = 2

在每个子任务中,有 12 数据集如下。

  1. (50分):5 \leq N \leq 7
  2. (50分):5 \leq N \leq 15
  3. (50分):5 \leq N \leq 30
  4. (50分):5 \leq N \leq 70
  5. (50分):5 \leq N \leq 200
  6. (50分):5 \leq N \leq 600
  7. (50分):5 \leq N \leq 2 \ 000
  8. (50分):5 \leq N \leq 8 \ 000
  9. (50分):5 \leq N \leq 50 \ 000
  10. (50分):5 \leq N \leq 200 \ 000
  11. (50分):5 \leq N \leq 500 \ 000
  12. (50分):5 \leq N \leq 1 \ 000 \ 000

注意:在每个数据集中,可以有两个或多个测试用例。


输入

输入由标准输入按以下格式给出:

N P
A_1 A_2 A_3 ... A_N

输出

打印可能的组合数 (X, Y, Z).


示例输入 1

5 1
3 1 6 4 8

示例输出 1

4

让 B_i 是这一天-2 参赛者得分 i.
有 4 方式如下。 X 是金牌得主的ID, Y ID 银牌获得者的 ID,以及 Z 是铜牌获得者的ID。

  • (X, Y, Z) = (5, 3, 1)。如果 B = (3, 4, 2, 1, 5),最终得分为 6, 5, 8, 5, 13。因此,它满足条件。
  • (X, Y, Z) = (5, 3, 2)。如果 B = (2, 4, 3, 1, 5),最终得分为 5, 5, 9, 5, 13。因此,根据抽签,有可能满足条件。
  • (X, Y, Z) = (5, 3, 4)。如果 B = (1, 2, 3, 4, 5),最终得分为 4, 3, 9, 8, 13。因此,它满足条件。
  • (X, Y, Z) = (5, 4, 1)。如果 B = (4, 2, 1, 3, 5),最终得分为 7, 3, 7, 7, 13。因此,根据抽签,有可能满足条件。

示例输入 2

5 2
6 4 1 7 2

示例输出 2

3

有 3 方式如下。

  • (X, Y, Z) = (4, 2, 1)。如果 B = (1, 5, 3, 4, 2),最终得分为 7, 9, 4, 11, 4。因此,它满足条件。
  • (X, Y, Z) = (4, 5, 1)。如果 B = (1, 2, 3, 4, 5),最终得分为 7, 6, 4, 11, 7。因此,根据抽签,有可能满足条件。
  • (X, Y, Z) = (4, 5, 2)。如果 B = (1, 3, 2, 4, 5),最终得分为 7, 7, 3, 11, 7。因此,根据抽签,有可能满足条件。

示例输入 3

10 1
6 4 11 14 3 17 13 18 8 10

示例输出 3

26

示例输入 4

10 2
18 14 19 4 12 1 7 15 9 5

示例输出 4

14