以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。




可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 3 – Sushi
回転寿司(Sushi)
回転寿司屋JOI では寿司の乗った皿を環状のベルトコンベアで運んでいる.ベルトコンベアは反時計回
りに回っている.現在,店内には客1 から客N までのN 人の客がいて,客はベルトコンベアの周りに番
号順に反時計回りに並んでいる.客N の隣には客1 が座っている.
客は1 人1 枚ずつの皿を持っている.各皿には価格と呼ばれる値が定まっており,店を出る際に,客は,
自分の持っている皿の価格に等しい金額を支払う.
回転寿司屋JOI では,一風変わったタイムセールを実施している.このタイムセールでは,Q 回に分け
て,順番に板前から皿が提供される.i 回目(1 ≦i ≦Q) の皿の提供の内容は3 個の整数の組(S i, Ti, Pi) で
表される.
タイムセールのルールは次の通りである.タイムセールが始まる直前に,板前はベルトコンベア上の皿
を全て回収する.以下の1~3 をi = 1, 2, . . . , Q まで繰り返す.
1. 板前がベルトコンベアの客S i の前の位置に,価格Pi の皿を置く.
2. 皿は客S i の場所から客Ti の場所までベルトコンベア上を移動する.それぞれの客は,自分の前の皿
に対し,次の行動を行う.
◦もし,その皿の価格が自分の持っている皿の価格より小さいならば,自分の皿とベルトコンベ
ア上の皿を交換する.
◦もし,その皿の価格が自分の持っている皿の価格以上であれば,皿の交換は行わない.
3. 皿が客Ti の前を通過した後,板前がその皿を回収する.
あなたは板前のもとで職人修業をしている弟子であり,店の皿洗いを任せられている.回転寿司屋JOI
の皿は価格によって洗い方が異なる.あなたは皿洗いの準備のために,タイムセールにおけるQ 回の提供
において板前がどの価格の皿を回収するのかをあらかじめ知っておきたい.
補足(競技終了後に追記)
S i = Ti のときは,客S i のみが2 つ目の行動を行う.
課題
それぞれの客がタイムセールの直前に持っている皿の情報と,タイムセールにおける皿の提供の情報が
与えられたとき,それぞれの皿の提供で板前が回収する皿の価格を求めるプログラムを作成せよ.
回転寿司– 1 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 3 – Sushi
入力
標準入力から以下のデータを読み込め.
• 1 行目には,整数N, Q が空白を区切りとして書かれている.これは,客の人数がN 人,タイムセー
ルにおける皿の提供回数がQ 回であることを表す.
• 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Xi が書かれている.これは,客i がタイムセールの
直前に価格Xi の皿を持っていることを表す.
• 続くQ 行のうちのi 行目(1 ≦i ≦Q) には,整数S i, Ti, Pi が空白を区切りとして書かれている.これ
は,i 回目の皿の提供が組(S i, Ti, Pi) で表されることを表す.
出力
出力はQ 行からなる.標準出力のi 行目(1 ≦i ≦Q) には,i 回目の皿の提供で板前が回収する皿の価格
を表す整数を出力せよ.
制限
すべての入力データは以下の条件を満たす.
• 1 ≦N ≦400 000.
• 1 ≦Q ≦25 000.
• 1 ≦Xi ≦1 000 000 000 (1 ≦i ≦N).
• 1 ≦S i ≦N (1 ≦i ≦Q).
• 1 ≦Ti ≦N (1 ≦i ≦Q).
• 1 ≦Pi ≦1 000 000 000 (1 ≦i ≦Q).
小課題
小課題1 [5 点]
以下の条件を満たす.
• N ≦2 000.
• Q ≦2 000.
回転寿司– 2 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 3 – Sushi
小課題2 [15 点]
以下の条件を満たす.
• S i = 1 (1 ≦i ≦Q).
• Ti = N (1 ≦i ≦Q).
小課題3 [80 点]
追加の制限はない.
入出力例
入力例1 出力例1
6 7 7
8 9
6 8
7 7
4 8
5 6
9 5
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3
客1 から客6 までの持っている皿の価格は,それぞれの皿の提供の後,以下のようになる.
• 1 回目の皿の提供の後,8, 5, 6, 4, 5, 9
• 2 回目の皿の提供の後,8, 5, 6, 4, 4, 5
• 3 回目の皿の提供の後,7, 5, 6, 4, 4, 5
• 4 回目の皿の提供の後,2, 5, 6, 4, 4, 5
• 5 回目の皿の提供の後,2, 5, 6, 4, 4, 5
• 6 回目の皿の提供の後,2, 5, 5, 1, 4, 4
回転寿司– 3 / 4
Japanese Olympiad in Informatics 2015/2016
Spring Training Camp/Qualifying Trial
March 19–25, 2016, Komaba/Yoyogi, Tokyo
Contest Day 3 – Sushi
• 7 回目の皿の提供の後,2, 5, 3, 1, 4, 4
入力例2 出力例2
4 2 7
5 5
2
4
7
1 4 3
1 4 1
入力例2 は,小課題2 の制限を満たす.
入力例3 出力例3
10 10 19
19 10
5 14
8 17
17 8
14 10
3 3
9 12
10 7
7 9
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3
回転寿司– 4 / 4