A - 年齢の差 (Age Difference)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 市には 1 から N までの番号が付けられた N 人の住民がおり，住民 i (1 \leqq i \leqq N) の年齢は A_i 歳である．

JOI 市の住民の年齢 A_1, A_2, \dots, A_N が与えられる．i = 1, 2, \dots, N に対して，住民 i と他の住民との年齢の差の最大値を求めるプログラムを作成せよ．

制約

  • 2 \leqq N \leqq 250\,000．
  • 0 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
  • 入力される値はすべて整数である．

小課題

  1. (25 点) N = 2．
  2. (30 点) N \leqq 1\,000．
  3. (45 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

N
A_1 A_2 \cdots A_N

出力

N 行出力せよ．i 行目 (1 \leqq i \leqq N) には，住民 i と他の住民との年齢の差の最大値を出力せよ．

入力例 1

3
13 15 20

出力例 1

7
5
7
  • 住民 1 と住民 2, 3 との年齢の差はそれぞれ 2, 7 歳である．これらの最大値は 7 歳であるから，1 行目には 7 を出力する．
  • 住民 2 と住民 1, 3 との年齢の差はそれぞれ 2, 5 歳である．これらの最大値は 5 歳であるから，2 行目には 5 を出力する．
  • 住民 3 と住民 1, 2 との年齢の差はそれぞれ 7, 5 歳である．これらの最大値は 7 歳であるから，3 行目には 7 を出力する．

この入力例は小課題 2, 3 の制約を満たす．

入力例 2

2
100 100

出力例 2

0
0
  • 住民 1 と住民 2 との年齢の差は 0 歳である．したがって，1 行目には 0 を出力する．
  • 住民 2 と住民 1 との年齢の差は 0 歳である．したがって，2 行目には 0 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 3

10
440894064 101089692 556439322 34369336 98417847 216265879 623843484 554560874 247445405 718003331

出力例 3

406524728
616913639
522069986
683633995
619585484
501737452
589474148
520191538
470557926
683633995

この入力例は小課題 2, 3 の制約を満たす．
B - ジョイ四人組 (JOI04)

Time Limit: 3 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI 中学校には 4N 人の一年生が在籍しており，4 つのクラスに分かれている．各クラスの情報は以下の通りである．

  • 1 年 A 組： N 人の生徒がいる．それぞれの生徒の身長は A_1, A_2, \ldots, A_N である．
  • 1 年 B 組： N 人の生徒がいる．それぞれの生徒の身長は B_1, B_2, \ldots, B_N である．
  • 1 年 C 組： N 人の生徒がいる．それぞれの生徒の身長は C_1, C_2, \ldots, C_N である．
  • 1 年 D 組： N 人の生徒がいる．それぞれの生徒の身長は D_1, D_2, \ldots, D_N である．

来月，JOI 中学校では体育祭が開催されることになった．体育祭には，リレー，騎馬戦，棒倒しなどの様々な種目があるが，各学年が踊るダンスは「体育祭の華」とも呼ばれる注目の種目である．

ここで一年生は，各クラスから代表を 1 人ずつ選び，4 人でダンスをすることになった．ダンスの見栄えをできるだけ良くするため，身長の差ができるだけ小さくなるように 4 人組を選ぶことにした．

一年生の身長が与えられるとき，「4 人の身長の最大値」と「4 人の身長の最小値」の差として考えられる最小の値を求めるプログラムを作成せよ．

制約

  • 1 \leqq N \leqq 75\,000．
  • 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
  • 1 \leqq B_j \leqq 10^9 (1 \leqq j \leqq N)．
  • 1 \leqq C_k \leqq 10^9 (1 \leqq k \leqq N)．
  • 1 \leqq D_l \leqq 10^9 (1 \leqq l \leqq N)．
  • 入力される値はすべて整数である．

小課題

  1. (7 点) N = 1．
  2. (23 点) N \leqq 30．
  3. (14 点) N \leqq 2\,000，A_i \leqq 10 (1 \leqq i \leqq N)，B_j \leqq 10 (1 \leqq j \leqq N)，C_k \leqq 10 (1 \leqq k \leqq N)，D_l \leqq 10 (1 \leqq l \leqq N)．
  4. (20 点) N \leqq 2\,000，A_i \leqq 2\,000 (1 \leqq i \leqq N)，B_j \leqq 2\,000 (1 \leqq j \leqq N)，C_k \leqq 2\,000 (1 \leqq k \leqq N)，D_l \leqq 2\,000 (1 \leqq l \leqq N)．
  5. (13 点) N \leqq 2\,000．
  6. (23 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

N
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_N
C_1 C_2 \cdots C_N
D_1 D_2 \cdots D_N

出力

「4 人の身長の最大値」と「4 人の身長の最小値」の差として考えられる最小の値を 1 行で出力せよ．

入力例 1

1
169
173
152
200

出力例 1

48

N = 1 なので，全員の生徒を選んで 4 人組を作らなければならない．このとき，4 人の身長の最大値は 200，最小値は 152 となり，その差は 200 - 152 = 48 である．よって，48 を出力する．

この入力例は小課題 1, 2, 4, 5, 6 の制約を満たす．

入力例 2

7
7 9 9 4 6 3 5
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

出力例 2

2

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす．

入力例 3

7
1 1 1 1 2 1 1
1 2 1 1 1 1 1
1 1 1 1 2 1 1
1 1 1 1 1 1 2

出力例 3

0

この入力例は小課題 2, 3, 4, 5, 6 の制約を満たす．

入力例 4

5
287 690 413 420 138
813 873 223 415 907
261 330 361 747 787
958 672 544 126 345

出力例 4

70

この入力例は小課題 2, 4, 5, 6 の制約を満たす．

入力例 5

10
1682 2008 1135 1576 2450 1362 1518 1925 2212 1275
1993 1945 1312 1401 2027 1705 1086 2333 1787 1654
2257 1548 1219 1031 2613 2171 1866 1532 2800 1497
1062 1175 1984 1870 2059 1639 2107 1335 1289 2494

出力例 5

79

この入力例は小課題 2, 5, 6 の制約を満たす．
C - 塗りつぶし (Painting)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

JOI くんはお絵かきソフトで遊んでいる．

お絵かきソフトでは，縦 H 行，横 W 列の長方形のマス目に絵を描くことができる．それぞれのマスには色が定められており，色は 1 以上 10^9 以下の整数で表される．

上から i 行目 (1 \leqq i \leqq H)，左から j 列目 (1 \leqq j \leqq W) のマスをマス (i,j) と呼ぶ．現在，マス (i,j) の色は A_{i,j} である．

マス (i,j) から辺で接しているマスへの移動を繰り返し，マス (i,j) と色が異なるマスに入ることなく移動できるマスの集まりを，ここではマス (i,j) の領域と呼ぶ．

お絵かきソフトには，塗りつぶしという機能がある．この機能では，あるマス (x,y) (1 \leqq x \leqq H，1 \leqq y \leqq W) と色 c (1 \leqq c \leqq 10^9) を指定すると，マス (x,y) の領域に含まれるマスの色がすべて c に変化する．

JOI くんはあるマス (x,y) と色 c を選び，そのマスと色を指定して塗りつぶしをちょうど 1 回使う．塗りつぶしを使った後のマス (x,y) の領域に含まれるマスの個数が JOI くんの得点となる．

JOI くんの得点として達成可能な最大値を求めるプログラムを作成せよ．

制約

  • 1 \leqq H \leqq 500．
  • 1 \leqq W \leqq 500．
  • 1 \leqq A_{i,j} \leqq 10^9 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
  • 入力される値はすべて整数である．

小課題

  1. (9 点) H = 1．
  2. (32 点) H \leqq 30，W \leqq 30，A_{i,j} \leqq 5 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
  3. (18 点) H \leqq 30，W \leqq 30．
  4. (10 点) A_{i,j} \leqq 2 (1 \leqq i \leqq H，1 \leqq j \leqq W)．
  5. (31 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}

出力

JOI くんの得点として達成可能な最大値を 1 行に出力せよ．

入力例 1

4 4
1 2 3 1
2 2 3 1
1 2 3 1
3 3 2 2

出力例 1

9

最初の時点で，マス (2,2) の領域に含まれるマスはマス (1,2), (2,1), (2,2), (3,2) の 4 個である．そのため，マス (2,2) と色 3 を指定して塗りつぶしを使うと，下図のように，これらの 4 マスの色が 3 に変化する．

塗りつぶしを使った後，マス (2,2) の領域に含まれるマスはマス (1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3,3), (4,1), (4,2) の 9 個になる．よって，JOI くんの得点は 9 となる．

JOI くんの得点を 10 以上にすることはできないので，9 を出力する．

この入力は小課題 2, 3, 5 の制約を満たす．

入力例 2

2 10
1 2 2 1 3 3 3 3 1 1
1 1 1 1 1 1 1 3 3 3

出力例 2

18

この入力は小課題 2, 3, 5 の制約を満たす．

入力例 3

5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

出力例 3

25

この入力は小課題 2, 3, 4, 5 の制約を満たす．
D - 貨物列車 (Freight Train)

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

IOI 鉄道は 1 本の鉄道路線を運営している．IOI 鉄道線には一直線上に並んだ N 個の駅があり，順に 1 から N までの番号が付けられている．各 i (1 \leqq i \leqq N - 1) に対して，駅 i と駅 i + 1 の間は線路で結ばれており，その長さは 1 である．

IOI 鉄道は貨物を取り扱っている．駅 2, 3, \ldots, N には貨物が 1 つずつ置かれており，駅 i (2 \leqq i \leqq N) に置かれている貨物の価値は A_i である．

IOI 鉄道は貨物列車を 1 編成所有している．この列車は最初駅 1 におり，IOI 鉄道線上を双方向に走行できる．それぞれの駅では，その駅に置いてある貨物を列車に積むことや，列車に積まれている貨物を下ろし，その駅に置いておくことができる．

この貨物列車を用いて 駅 2, 3, \ldots, N に置かれている貨物を駅 1 に輸送したい．ただし，この列車には貨物を W 個以下しか載せることができない．すなわち，どの時点においても列車に貨物が W + 1 個以上載っていることは許されない．また，この列車は燃料の都合上，最大でも総距離 D しか走行することができない．そのため，すべての貨物を駅 1 に輸送することはできないかもしれない．

IOI 鉄道の社長である JOI くんは，この条件のもと適切に貨物列車を走行させることで，最終的に駅 1 に置かれている貨物の価値の合計をなるべく大きくしたい．

貨物列車の情報と各駅に置かれている貨物の情報が与えられたとき，最終的に駅 1 に置かれている貨物の価値の合計として達成可能な最大値を求めるプログラムを作成せよ．

制約

  • 2 \leqq N \leqq 450．
  • 1 \leqq W \leqq N - 1．
  • 2 \leqq D \leqq N^2 - N．
  • 1 \leqq A_i \leqq 1\,000\,000 (2 \leqq i \leqq N)．
  • 入力される値はすべて整数である．

小課題

  1. (6 点) W = 1，A_i = 1 (2 \leqq i \leqq N)．
  2. (9 点) A_i = 1 (2 \leqq i \leqq N)．
  3. (24 点) W = 1．
  4. (13 点) N \leqq 15．
  5. (24 点) N \leqq 50．
  6. (24 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

N W D 
A_2 A_3 \cdots A_N

出力

最終的に駅 1 に置かれている貨物の価値の合計として達成可能な最大値を 1 行で出力せよ．

入力例 1

4 1 10
1 1 1

出力例 1

2

例えば，以下のように貨物列車を走行させると最終的に駅 1 に置かれている貨物の価値の合計を 2 にすることができる．

最初，貨物列車は駅 1 にいる．

  1. 貨物列車を駅 2 に走行させる．
  2. 駅 2 に置かれている価値 1 の貨物を貨物列車に積む．
  3. 貨物列車を駅 1 に走行させる．
  4. 貨物列車に積まれている価値 1 の貨物を駅 1 に置く．
  5. 貨物列車を駅 4 に走行させる．
  6. 駅 4 に置かれている価値 1 の貨物を貨物列車に積む．
  7. 貨物列車を駅 1 に走行させる．
  8. 貨物列車に積まれている価値 1 の貨物を駅 1 に置く．

列車の走行した総距離は 8 であり，列車が総距離 10 以下しか走行できないという条件を満たしている．

このとき，最終的に駅 1 に置かれている貨物の価値の合計は 2 である．最終的に駅 1 に置かれている貨物の価値の合計を 3 以上にすることはできないため，2 を出力する．

この入力例はすべての小課題の制約を満たす．

入力例 2

7 3 16
1 1 1 1 1 1

出力例 2

5

例えば，以下のように貨物列車を走行させると最終的に駅 1 に置かれている貨物の価値の合計を 5 にすることができる．

最初，貨物列車は駅 1 にいる．

  1. 貨物列車を駅 5 に走行させる．
  2. 駅 5 に置かれている価値 1 の貨物を貨物列車に積む．
  3. 貨物列車を駅 6 に走行させる．
  4. 駅 6 に置かれている価値 1 の貨物を貨物列車に積む．
  5. 貨物列車を駅 1 に走行させる．
  6. 貨物列車に積まれている 2 つの価値 1 の貨物をすべて駅 1 に置く．
  7. 貨物列車を駅 2 に走行させる．
  8. 駅 2 に置かれている価値 1 の貨物を貨物列車に積む．
  9. 貨物列車を駅 3 に走行させる．
  10. 駅 3 に置かれている価値 1 の貨物を貨物列車に積む．
  11. 貨物列車を駅 4 に走行させる．
  12. 駅 4 に置かれている価値 1 の貨物を貨物列車に積む．
  13. 貨物列車を駅 1 に走行させる．
  14. 貨物列車に積まれている 3 つの価値 1 の貨物をすべて駅 1 に置く．

列車の走行した総距離は 16 であり，列車が総距離 16 以下しか走行できないという条件を満たしている．

このとき，最終的に駅 1 に置かれている貨物の価値の合計は 5 である．最終的に駅 1 に置かれている貨物の価値の合計を 6 以上にすることはできないため，5 を出力する．

この入力例は小課題 2, 4, 5, 6 の制約を満たす．

入力例 3

5 2 12
40 30 20 10

出力例 3

100

例えば，以下のように貨物列車を走行させると最終的に駅 1 に置かれている貨物の価値の合計を 100 にすることができる．

最初，貨物列車は駅 1 にいる．

  1. 貨物列車を駅 5 に走行させる．
  2. 駅 5 に置かれている価値 10 の貨物を貨物列車に積む．
  3. 貨物列車を駅 4 に走行される．
  4. 駅 4 に置かれている価値 20 の貨物を貨物列車に積む．
  5. 貨物列車を駅 2 に走行させる．
  6. 貨物列車に積まれている価値 10 の貨物と価値 20 の貨物を駅 2 に置く．
  7. 駅 2 に置かれている価値 40 の貨物を貨物列車に積む．
  8. 貨物列車を駅 3 に走行させる．
  9. 駅 3 に置かれている価値 30 の貨物を貨物列車に積む．
  10. 貨物列車を駅 1 に走行させる．
  11. 貨物列車に積まれている価値 30 の貨物と価値 40 の貨物を駅 1 に置く．
  12. 貨物列車を駅 2 に走行させる．
  13. 駅 2 に置かれている価値 10 の貨物と価値 20 の貨物を貨物列車に積む．
  14. 貨物列車を駅 1 に走行させる．
  15. 貨物列車に積まれている価値 10 の貨物と価値 20 の貨物を駅 1 に置く．

列車の走行した総距離は 12 であり，列車が総距離 12 以下しか走行できないという条件を満たしている．

このとき，最終的に駅 1 に置かれている貨物の価値の合計は 100 である．最終的に駅 1 に置かれている貨物の価値の合計を 101 以上にすることはできないため，100 を出力する．

この入力例は小課題 4, 5, 6 の制約を満たす．

入力例 4

5 1 11
2 7 1 8

出力例 4

10

この入力例は小課題 3, 4, 5, 6 の制約を満たす．

入力例 5

9 3 14
54640 754112 604290 105866 591907 801383 502975 379373

出力例 5

2214425

この入力例は小課題 4, 5, 6 の制約を満たす．
E - 日本沈没 2 (Japan Sinks 2)

Time Limit: 3 sec / Memory Limit: 1024 MB

配点： 100 点

問題文

日本列島は東西に細長い列島である．日本列島は南北方向の境界線により N 個の区画に分けられている．区画には西から順に 1 から N までの番号が付けられている．現在，区画 i (1 \leqq i \leqq N) の標高は A_i \: \mathrm{m} である．

日本列島ではたびたび嵐が起きている．嵐が起きると波による浸食で各区画の標高が以下のように減少する．

  • 強さ x の西風の嵐では，西から数えて x 個以内の区画のうち，「それより西に自身より標高の高い区画が存在しない」ようなすべての区画の標高が 1 \: \mathrm{m} 減少する．すなわち，嵐の前の区画 i の標高を a_i で表すと，i \leqq x かつ，1 \leqq k \lt i となるすべての k に対して a_k \leqq a_i となる場合に区画 i の標高は 1 \: \mathrm{m} 減り，それ以外の場合には変わらない．
  • 強さ x の東風の嵐では，東から数えて x 個以内の区画のうち，「それより東に自身より標高の高い区画が存在しない」ようなすべての区画の標高が 1 \: \mathrm{m} 減少する．すなわち，嵐の前の区画 i の標高を a_i で表すと，i \geqq N - x + 1 かつ，i \lt k \leqq N となるすべての k に対して a_k \leqq a_i となる場合に区画 i の標高は 1 \: \mathrm{m} 減り，それ以外の場合には変わらない．

あなたは，今後 Q 日間の出来事をシミュレーションしなければならない．j 日目 (1 \leqq j \leqq Q) には次のような出来事が起きる．

  • T_j = 1 のとき，強さ X_j の西風の嵐が起きる．
  • T_j = 2 のとき，強さ X_j の東風の嵐が起きる．
  • T_j = 3 のとき，その時点での区画 X_j の標高を報告する．

なお，制約より，どの区画の標高も負にならないことが保証される．

現在の各区画の標高および今後 Q 日間の出来事が与えられるので，T_j = 3 である日に対して，指定された区画の標高を求めるプログラムを作成せよ．

制約

  • 1 \leqq N \leqq 300\,000．
  • 1 \leqq Q \leqq 300\,000．
  • Q \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
  • 1 \leqq T_j \leqq 3 (1 \leqq j \leqq Q)．
  • 1 \leqq X_j \leqq N (1 \leqq j \leqq Q)．
  • 入力される値はすべて整数である．

小課題

  1. (5 点) N \leqq 2\,000，Q \leqq 2\,000．
  2. (27 点) T_j \neq 3 ならば X_j = N (1 \leqq j \leqq Q).
  3. (28 点) A_1 = A_2 = \cdots = A_N = Q．
  4. (20 点) T_j \neq 2 (1 \leqq j \leqq Q)．
  5. (20 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

N Q
A_1 A_2 \dots A_N
T_1 X_1
T_2 X_2
\vdots
T_Q X_Q

出力

T_j = 3 である j (1 \leqq j \leqq Q) それぞれに対して，j 日目時点での区画 X_j の標高 (\mathrm{m}) を表す整数を，1 行ずつ順に出力せよ．

入力例 1

5 7
7 7 7 7 7
1 3
1 1
3 1
2 1
2 5
3 2
3 4

出力例 1

5
6
6
区画 1, 2, 3, 4, 5 の標高 (\mathrm{m}) 出来事
開始時 7, 7, 7, 7, 7
1 日目 強さ 3 の西風の嵐が起きる．
西から 3 個以内の区画で，「それより西に自分より標高の高い区画が存在しない」ものは区画 1, 2, 3 である．
6, 6, 6, 7, 7
2 日目 強さ 1 の西風の嵐が起きる．
西から 1 個以内の区画で，「それより西に自分より標高の高い区画が存在しない」ものは区画 1 のみである．
5, 6, 6, 7, 7
3 日目 区画 1 の標高は現在 5 \: \mathrm{m} なので，5 を出力する．
5, 6, 6, 7, 7
4 日目 強さ 1 の東風の嵐が起きる．
東から 1 個以内の区画で，「それより東に自分より標高の高い区画が存在しない」ものは区画 5 のみである．
5, 6, 6, 7, 6
5 日目 強さ 5 の東風の嵐が起きる．
東から 5 個以内の区画で，「それより東に自分より標高の高い区画が存在しない」ものは区画 4, 5 のみである．
5, 6, 6, 6, 5
6 日目 区画 2 の標高は現在 6 \: \mathrm{m} なので，6 を出力する．
5, 6, 6, 6, 5
7 日目 区画 4 の標高は現在 6 \: \mathrm{m} なので，6 を出力する．

この入力例は小課題 1, 3, 5 の制約を満たす．

入力例 2

5 7
10 13 14 7 12
1 5
2 5
3 3
3 4
2 5
3 1
3 2

出力例 2

12
7
9
11

この入力例は小課題 1, 2, 5 の制約を満たす．

入力例 3

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

出力例 3

7
9
6
6

この入力例は小課題 1, 4, 5 の制約を満たす．

入力例 4

5 6
6 8 6 9 7
2 1
2 4
3 5
1 5
3 4
3 3

出力例 4

5
7
6

この入力例は小課題 1, 5 の制約を満たす．