#PQJ1551x409. QOJ 1551_409

    ID: 2655 传统题 9000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训模拟排序

QOJ 1551_409

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