舞踏会 (Ball)

#「JOI 2014/2015 决赛」舞会 ## 题目描述 **译自 [JOI 2014/2015 决赛](https://www.ioi-jp.org/joi/2014/2015-ho/index.html) T4「[舞踏会](https://www.ioi-jp.org/joi/2014/2015-ho/2015-ho.pdf)」** IOI 王国为了庆祝 JOI 公主的生日，举行了舞会。 预定有 $ N $ 位贵族要参加舞会。 $ N $ 是奇数。将贵族们从 $ 1 $ 到 $ N $ 编号。每个贵族有一个由整数表示的**舞蹈熟练度** 。贵族 $ i(1 \leq i \leq N) $ 舞蹈熟练度为 $ D_i $。 舞会中，含 JOI 公主在内的 $ N+1 $ 人两两一组跳舞。 IOI 王国遵循老手帮新手的传统，按以下方法决定跳舞的分组。 - 开始时， $ N $ 个贵族排成一列。 - 直到队列中只剩下一个贵族为止，不断进行以下操作。 - 调查最前面 $ 3 $ 个贵族的舞蹈熟练度。 - 这 $ 3 $ 个人中舞蹈熟练度最大的贵族称为 $ A $ 。如果存在多个人，从中选出序号最小的称为 $ A $ 。 - 这 $ 3 $ 个人中舞蹈熟练度最小的贵族称为 $ B $ 。如果存在多个人，从中选出序号最大的称为 $ B $ 。 - $ A $ 和 $ B $ 离开队列并组成一组。 - 这三人中没有被选择的一个人移动到队列最后。 - 最后剩下的一个人和 JOI 公主一组。 从第 $ 1 $ 个贵族到第 $ M(1 \leq M \leq N-2) $ 个贵族的 $ M $ 个贵族已经决定了自己开始时排在队列的第几个。剩下的 $ N-M $ 个贵族的排列方式可以由国王自由决定。 因为 JOI 公主才刚开始学跳舞，国王想知道和 JOI 公主组队的贵族的舞蹈熟练度的最大值。 #### 任务 给出每个贵族的舞蹈熟练度，和 $ M $ 个贵族开始时在队列中的位置。请编写程序求出和 JOI 公主一组的贵族的舞蹈熟练度的最大值。 第一行为两个以空格分开的整数 $ N,M $ 。分别表示舞会有 $ N $ 个贵族参加，已经决定排列位置的贵族有 $ M $ 人。 接下来 $ M $ 行中，第 $ i $ 行 $ (1\leq i \leq M) $ 为两个以空格分开的整数 $ D_i,P_i $ 。分别表示第 $ i $ 个贵族的舞蹈熟练度为 $ D_i $。贵族 $ i $ 开始时排在队列的第 $ P_i $ 位。 接下来 $ N-M $ 行中，第 $ i $ 行 $ (1\leq i \leq N-M) $ 为一个整数 $ D_{i+M} $。表示贵族 $(i+M)$ 的舞蹈的熟练度为 $ D_{i+M} $。 输出一行：表示和 JOI 公主组队的贵族的舞蹈熟练度的最大值。 #### 输入样例 1 ```plain 7 3 5 2 5 5 8 6 6 2 8 9 ``` #### 输出样例 1 ```plain 8 ``` #### 样例解释 1 开始时有 $ 3 $ 个人的位置是确定的。  括号内的数字表示舞蹈的熟练度，左端是队列的开始。 举例来说，考虑从队首开始的贵族的序号分别为$5,1,4,6,2,3,7$时：  这时队列会依次发生以下变化： - 队列最前面的 $ 3 $ 个贵族（贵族 $ 5 $ ，贵族 $ 1 $ ，贵族 $ 4 $ ） 中，舞蹈熟练度最大的人（贵族 $ 4 $ ）和舞蹈熟练度最小的人（贵族 $ 5 $ ）组队，剩下的贵族 $ 1 $ 移动到队尾。 - 接下来，队列最前面的 $ 3 $ 个贵族（贵族 $ 6 $ ，贵族 $ 2 $ ，贵族 $ 3 $ ） 中，舞蹈熟练度最大的人有两个：贵族 $ 6 $ 和贵族 $ 3 $ ，其中序号比较小的为贵族 $ 3 $ 。而前 $ 3 $ 人中舞蹈熟练度最小的人为贵族 $ 2 $ ，所以贵族 $ 3 $ 和贵族 $ 2 $ 组队。剩下的贵族 $ 6 $ 移动到队尾。 - 接下来，队列最前面的 $ 3 $ 个贵族（贵族 $ 7 $ ，贵族 $ 1 $ ，贵族 $ 6 $ ） 中，舞蹈熟练度最大的人（贵族 $ 7 $ ）和舞蹈熟练度最小的人（贵族 $ 1 $ ）组队，剩下的贵族 $ 6 $ 移动到队尾。 - 最后剩下的是贵族 $ 6 $ ，他将和 JOI 公主一组。 贵族 $ 6 $ 的舞蹈熟练度为 $ 8 $ ，这就是和 JOI 公主一组的贵族舞蹈熟练度最大值。  #### 输入样例 2 ```plain 3 1 5 3 5 5 ``` #### 输出样例 2 ```plain 5 ``` #### 输入样例 3 ```plain 7 2 32 4 27 6 37 41 41 30 27 ``` #### 输出样例 3 ```plain 37 ``` 对于 $8\%$ 的数据： - $N \leq 9$ 对于另 $16\%$ 的数据： - $N \leq 19$ 对于另 $44\%$ 的数据： - $N \leq 1999$ 对于 $100\%$ 的数据， - $3 \leq N \le 99999$ - $ N $ 为奇数 - $1 \leq D_i \leq 10^9 (1 \leq i \leq N)$ - $1 \leq P_i \leq N (1 \leq i \leq M)$ - $P_i \not = P_j (1 \leq i\lt j \leq M)$ 感谢 Planet6174 提供的翻译

[problemUrl]: https://atcoder.jp/contests/joi2015ho/tasks/joi2015ho_d IOI 王国では，王女である JOI 姫の誕生日を祝って舞踏会が開かれることになった． 舞踏会には $ N $ 人の貴族が参加する予定である．$ N $ は奇数である．貴族には $ 1 $ から $ N $ までの番号が付けられている．それぞれの貴族には踊りのうまさという整数が定められており，貴族 $ i $ ($ 1\ \leqq\ i\ \leqq\ N $) の踊りのうまさは $ D_i $ である． 舞踏会では JOI 姫を含む $ N\ +\ 1 $ 人で $ 2 $ 人ずつ組を作って踊る．IOI 王国では，上級者が初級者を補助できるように，伝統的に以下の方法で踊りの組を決定している． - 最初に，$ N $ 人の貴族が $ 1 $ 列に並ぶ． - 列に並んでいる貴族が $ 1 $ 人になるまで，以下の操作を繰り返す． - 列の先頭から $ 3 $ 人の貴族の踊りのうまさを調べる． - その $ 3 $ 人の貴族の中で，最も踊りのうまさが大きい貴族を $ A $ とおく．ただし，複数いる場合は，最も踊りのうまさが大きい貴族の中で，最も番号の小さい貴族 を $ A $ とおく． - その $ 3 $ 人の貴族の中で，最も踊りのうまさが小さい貴族を $ B $ とおく．ただし，複数いる場合は，最も踊りのうまさが小さい貴族の中で，最も番号の大きい貴族 を $ B $ とおく． - $ A $ と $ B $ が列から抜けて組になる． - 残った $ 1 $ 人は列の最後尾に移動する． - 最終的に残った $ 1 $ 人が JOI 姫と組になる．貴族 $ 1 $ から貴族 $ M $ ($ 1\ \leqq\ M\ \leqq\ N\ -\ 2 $) の $ M $ 人の貴族については，すでに初期状態で列の何番目に並ぶのかが決まっている．残りの $ N\ -\ M $ 人の貴族の並び方は国王が自由に決めることができる． JOI 姫は踊りを学んだばかりなので，国王は JOI 姫と組になる貴族の踊りのうまさをできるだけ大きくしたいと考えている．JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めよ．

標準入力から以下のデータを読み込め． - $ 1 $ 行目には，$ 2 $ 個の整数 $ N,\ M $ が空白を区切りとして書かれている．これは舞踏会に貴族が $ N $ 人参加し，列に並ぶ場所がすでに決まっている貴族が $ M $ 人いることを表す． - 続く $ M $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ M $) には，$ 2 $ 個の整数 $ D_i,\ P_i $ が空白を区切りとして書かれている．これは貴族 $ i $ の踊りのうまさが $ D_i $ で，貴族 $ i $ が初期状態で列の先頭から $ P_i $ 番目に並ぶことを表す． - 続く $ N\ -\ M $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N\ -\ M $) には，整数 $ D_{i\ +\ M} $ が書かれている．これは貴族 ($ i\ +\ M $) の踊りのうまさが $ D_{i\ +\ M} $ であることを表す．

標準出力に，JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を表す整数を $ 1 $ 行で出力せよ． - - - - - -

7 3
5 2
5 5
8 6
6
2
8
9

8

3 1
5 3
5
5

5

7 2
32 4
27 6
37
41
41
30
27

37

### 課題 それぞれの貴族の踊りのうまさと，$ M $ 人の貴族の初期状態で並ぶ場所が与えられたとき，JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 3\ \leqq\ N\ \leqq\ 99\,999 $． - $ N $ は奇数である． - $ 1\ \leqq\ M\ \leqq\ N\ -\ 2 $． - $ 1\ \leqq\ D_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ 1\ \leqq\ P_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ P_i\ \neq\ P_j $ ($ 1\ \leqq\ i\ <\ j\ \leqq\ M $)． ### 小課題 #### 小課題 1 \[8 点\] - $ N\ \leqq\ 9 $ を満たす． #### 小課題 2 \[16 点\] - $ N\ \leqq\ 19 $ を満たす． #### 小課題 3 \[44 点\] - $ N\ \leqq\ 1\,999 $ を満たす． #### 小課題 4 \[32 点\] 追加の制限はない． - - - - - - ### Sample Explanation 1 初期状態では $ 3 $ 人の貴族の並ぶ場所がすでに決まっている． !\[\](https://img.atcoder.jp/joi2015ho/d-1.png)括弧内の数字は踊りのうまさを表す．左端が列の先頭である． 例えば，先頭から順に貴族 $ 5 $，貴族 $ 1 $，貴族 $ 4 $，貴族 $ 6 $，貴族 $ 2 $，貴族 $ 3 $，貴族 $ 7 $ という順番に並んだ場合を考える． !\[\](https://img.atcoder.jp/joi2015ho/d-2.png)すべての貴族が並んだあとの配置 この場合，以下のように列が変化していく． - 列の先頭の $ 3 $ 人の貴族 (貴族 $ 5 $，貴族 $ 1 $，貴族 $ 4 $) 中で，最も踊りのうまさが大きい貴族 $ 4 $ と最も踊りのうまさが小さい貴族 $ 5 $ が組になり，残った貴族 $ 1 $ が最後尾に移動する． - 次に，列の先頭の $ 3 $ 人の貴族 (貴族 $ 6 $，貴族 $ 2 $，貴族 $ 3 $) の中で，最も踊りのうまさが大きい貴族は貴族 $ 6 $ と貴族 $ 3 $ の $ 2 $ 人であり，このうち番号の小さい貴族は貴族 $ 3 $ である．また，列の先頭の $ 3 $ 人の貴族のうち最も踊りのうまさが小さい貴族は貴族 $ 2 $ である．貴族 $ 3 $ と貴族 $ 2 $ が組になり，残った貴族 $ 6 $ が最後尾に移動する． - 次に，列の先頭の $ 3 $ 人の貴族 (貴族 $ 7 $，貴族 $ 1 $，貴族 $ 6 $) の中で，最も踊りのうまさが大きい貴族 $ 7 $ と最も踊りのうまさが小さい貴族 $ 1 $ が組になり，残った貴族 $ 6 $ が最後尾に移動する． - 最終的に貴族 $ 6 $ が残り，JOI 姫と組になる．貴族 $ 6 $ の踊りのうまさは $ 8 $ である．この値が JOI 姫と組になる貴族の踊りのうまさとして考えられる最大値である． !\[\](https://img.atcoder.jp/joi2015ho/d-3.png)列の変化の様子 - - - - - - ### Sample Explanation 2 どのような順番で並んでも，貴族 $ 2 $ と JOI 姫が組になる． - - - - - -