← 返回题目列表

AtCoder · abc013_4

D. 阿弥陀佛

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

問題文

你知道自古流传下来的日本传统彩票阿弥陀寺吗?

玩阿弥陀寺时,首先 N 在书上画平行垂直线。接下来,M 将书本的水平线画入其中。每条水平线彼此相邻 2 必须绘制书本的垂直线以将它们连接起来。2 同一高度的水平线不得超过一条。在这里,从上面 i (1\,≦\,i\,≦\,M) 从左侧算起的第 3 条水平线 A_i (1\,≦\,A_i < N)第垂直线和 假设我们要连接第 A_i + 1 条垂直线。

N = 5, M = 7, A = \{1,4,3,4,2,3,1\} 案例中的 Amida 彩票如下所示。抽签时,画垂直线 1 选择一本书,然后从上往下走。如果途中遇到水平线,一定要转弯,不要顺着垂直线向上。比如这张阿弥陀寺,从左边开始 如果您从左侧第 4 条垂直线开始抽签 我们到达了第 3 条垂直线。

到目前为止,这都是一个正常的故事,但这些天,“大数据”这个词被谈论得很多。阿弥陀寺未来为了生存,也必须做大,与大数据竞争。

所以,我垂直放置阿弥陀寺。 D 让我们考虑通过将它们连接在一起来制作一个巨大的阿弥陀寺。比如前面提到的阿弥陀寺 如果连接 2 块,它将如下所示。在这种情况下,从左边开始 如果您从第 4 条垂直线开始抽签,您将到达的地方将从左侧开始。 成为第 5 条垂直线。

庞大的阿弥陀彩就这样被创造出来了,但如果阿弥陀彩不能实现它最初的目的,那么做大也是没有意义的。换句话说,如果你不能有效地计算出这个巨型阿弥陀佛的抽奖结果,那么你创造的巨型阿弥陀佛就只是一个涂鸦。

所以, 所有满足1\,≦\,k\,≦\,N 的整数 k 从巨人阿弥陀寺的左边开始 如果您选择第 k 条垂直线并沿着该线移动,我希望您编写一个程序来计算从底部左侧开始的垂直线数。


入力

输入是按以下格式从标准输入给出的。

N M D
A_1 A_2 ... A_M
  • 1 行是一个整数,表示原始阿弥陀寺中垂直行的数量。 N (2\,≦\,N\,≦\,10^5),表示水平线数的整数 M (0\,≦\,M\,≦\,2 \times 10^5),表示原始阿弥陀佛垂直连接次数的整数 D (1\,≦\,D\,≦\,10^9) 用空格分隔。
  • 2 线代表原始阿弥陀寺中水平线的信息。 M 整数 A_i (1\,≦\,i\,≦\,M) 用空格分隔。

部分点

这个问题的测试用例是 4 分为两组,每组都分配分数。

  • 1 第三组中,测试用例是 D = 1 满意。如果您正确回答了该组中的所有测试用例, 10 点。
  • 2 第三组中,测试用例是 N\,≦\,1,000 和 D\,≦\,1,000 满意。如果您正确回答了该组中的所有测试用例, 20 点。
  • 3 第三组中,测试用例是 N\,≦\,8 满意。如果您正确回答了该组中的所有测试用例, 20 点。
  • 4 在第二组中,对测试用例没有额外的限制。如果您正确回答了该组中的所有测试用例, 输出 50 点。

出力

N 行。其中 k 在这一排,从巨人阿弥陀寺的左边开始 当您选择第 k 条垂直线并沿着该线移动时,输出一个整数,表示从底端左侧开始到达的垂直线数。

还在输出末尾包含换行符。


入力例1

5 7 1
1 4 3 4 2 3 1

出力例1

4
2
5
3
1

此输入/输出示例对应于问题文本中第一张图所示的 Amidakuji。


入力例2

5 7 2
1 4 3 4 2 3 1

出力例2

3
2
1
5
4

该输入/输出示例是 它对应于第 2 图中所示的阿弥陀寺。这个案例是 1 请注意,不满足第二个测试组的约束。


入力例3

10 20 300
9 1 2 5 8 1 9 3 5 6 4 5 4 6 8 3 2 7 9 6

出力例3

3
7
2
4
5
9
6
1
8
10

这个案例是 1 津和 3 请注意,不满足第二个测试组的约束。