← 返回题目列表

AtCoder · joisc2021_c

C. 美食广场

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

以下是来自日本的原始新闻PDF,已完整保存和染色。

フードコート (Foodcourt) - 原题 PDF 第 1 页
原题PDF第1页
フードコート (Foodcourt) - 原题 PDF 第 2 页
原题PDF第2页
フードコート (Foodcourt) - 原题 PDF 第 3 页
原题PDF第3页
フードコート (Foodcourt) - 原题 PDF 第 4 页
原题PDF第4页
フードコート (Foodcourt) - 原题 PDF 第 5 页
原题PDF第5页
フードコート (Foodcourt) - 原题 PDF 第 6 页
原题PDF第6页
可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                     Contest Day 1 – Food Court

             フードコート(Food Court)



 合宿施設であるIOI センターには,団体客専用のフードコートがある.フードコートにはN 軒の店舗が

横一列に並んでおり,1 からN までの番号が付けられている.各店舗の前には客が一列に並ぶ待機列が1

つずつある.

 今日IOI センターにはM 個の団体が宿泊しており,1 からM までの番号が付けられている.それぞれの

団体客は互いに会話を楽しむため,奇妙な並び方をする.

 このフードコートでは,待機列の客にデザートをおまけすることがある.ここでアルバイトをしている

JOI 君の仕事は,どの団体の客にデザートをおまけしたかを記録することである.

 開店前に待機列に並んでいる人はいない.今日の開店から閉店までに,待機列でQ 回の出来事が起きた

ことが分かっている.i 回目(1 ≦i ≦Q) の出来事は以下のいずれかである.

   加入番号がLi 以上Ri 以下の店舗の待機列の末尾に,団体Ci に属する客がKi 人ずつ加わった.
   脱退番号がLi 以上Ri 以下の店舗の待機列のうち,Ki 人以上の客が並んでいるものからは先頭から
      ちょうどKi 人が,Ki 人未満の客が並んでいるものからは全員が,待機列を去った.
 サービスその時点で店舗Ai の待機列にBi 人以上の客がいた場合,先頭からBi 人目の客にデザートをお

     まけした.そうでない場合,店員がデザートを食べた.

  JOI 君はどの団体の客にデザートをおまけしたかの記録を紛失してしまったので,上に挙げたQ 回の出

来事の情報を用いて記録を復元することにした.

 店舗の数,団体の数,出来事の数,および出来事の内容が与えられたとき,各「サービス」でデザートを

客におまけしたかを判定し,またデザートを客におまけしていればその客が属する団体の番号を求めるプロ

グラムを作成せよ.





                     フードコート– 1 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                     Contest Day 1 – Food Court



入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N M Q

      (Query 1)
                                 ...

      (Query Q)

  各(Query i) (1 ≦i ≦Q) にはいくつかの整数が空白区切りで書かれている.そのうち1 個目の整数をTi

とすると,この行の内容は以下のいずれかである.

    • Ti = 1 のとき,この行には続いて4 個の整数Li, Ri,Ci, Ki がこの順に書かれている.これはi 回目の
   出来事が「加入」で,番号がLi 以上Ri 以下の店舗の待機列の末尾に,団体Ci に属する客がKi 人ず

   つ加わったことを表す.

    • Ti = 2 のとき,この行には続いて3 個の整数Li, Ri, Ki がこの順に書かれている.これはi 回目の出
   来事が「脱退」で,番号がLi 以上Ri 以下の店舗の待機列のうち,Ki 人以上の客が並んでいる待機列
   からは先頭からちょうどKi 人が,Ki 人未満の客が並んでいる待機列からは全員が,待機列を去った

   ことを表す.

    • Ti = 3 のとき,この行には続いて2 個の整数Ai, Bi がこの順に書かれている.これはi 回目の出来事
   が「サービス」で,その時点で店舗Ai の待機列にBi 人以上の客がいた場合は先頭からBi 人目の客

   にデザートをおまけし,そうでない場合は店員がデザートを食べたことを表す.


出力

 「サービス」,つまりTi = 3 となる出来事i (1 ≦i ≦Q) それぞれに対して,その時にデザートを客におま
けしている場合はその客が属する団体の番号を,店員がデザートを食べた場合は0 を,標準出力に1 行ずつ

出力せよ.





                     フードコート– 2 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                     Contest Day 1 – Food Court



制約

    • 1 ≦N ≦250 000.

    • 1 ≦M ≦250 000.

    • 1 ≦Q ≦250 000.
    • Ti は1, 2, 3 のいずれかである(1 ≦i ≦Q).
    • Ti = 1 のとき,1 ≦Li ≦Ri ≦N,1 ≦Ci ≦M,1 ≦Ki ≦1 000 000 000 (1 ≦i ≦Q).
    • Ti = 2 のとき,1 ≦Li ≦Ri ≦N,1 ≦Ki ≦1 000 000 000 (1 ≦i ≦Q).
    • Ti = 3 のとき,1 ≦Ai ≦N,1 ≦Bi ≦1 000 000 000 000 000 (= 1015) (1 ≦i ≦Q).
    • Ti = 3 となるi (1 ≦i ≦Q) が1 つ以上存在する.


小課題

    1. (2 点) N ≦2 000,Q ≦2 000.Ti = 1 またはTi = 2 を満たす出来事i (1 ≦i ≦Q) に対してKi = 1.
    2. (5 点) N ≦2 000,Q ≦2 000.
    3. (7 点) N ≦65 000,Q ≦65 000.Ti = 1 を満たす出来事i (1 ≦i ≦Q) に対してRi −Li ≦10,Ki = 1.
    4. (21 点) M = 1.
    5. (15 点) N ≦65 000,Q ≦65 000.Ti = 1 またはTi = 2 を満たす出来事i (1 ≦i ≦Q) に対してKi = 1.
    6. (13 点) N ≦65 000,Q ≦65 000.Ti = 1 またはTi = 3 (1 ≦i ≦Q).
    7. (26 点) N ≦65 000,Q ≦65 000.

    8. (11 点) 追加の制約はない.





                     フードコート– 3 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                     Contest Day 1 – Food Court



入出力例

  入力例1              出力例1

   3 5 7                          2

   1 2 3 5 2                      0

   1 1 2 2 4                      4

   3 2 3

   2 1 3 3

   3 1 2

   1 2 3 4 2

   3 3 2

 以下の説明では各待機列を表記するとき,並んでいる客を先頭から順に所属する団体の番号に置き換えた

数列で表す.例えば,ある店舗の待機列に3 人の客が並んでいて,客の所属する団体の番号が先頭から順に

1, 2, 2 である場合,(1, 2, 2) と表す. また,空の待機列は() と表す.

 この入力例では,次の7 回の出来事が順に起きた.

    1. 出来事1 は「加入」であり,店舗2, 3 の待機列の末尾に団体5 の客が2 人ずつ加わった.この直後,

    店舗1, 2, 3 の待機列はそれぞれ(), (5, 5), (5, 5) となった.

    2. 出来事2 は「加入」であり,店舗1, 2 の待機列の末尾に団体2 の客が4 人ずつ加わった.この直後,

    店舗1, 2, 3 の待機列はそれぞれ(2, 2, 2, 2), (5, 5, 2, 2, 2, 2), (5, 5) となった.

    3. 出来事3 は「サービス」である.店舗2 の待機列には6 人の客がおり,これは3 人以上であるため,

   先頭から3 人目の客にデザートをおまけした.この客は団体2 に属するため,2 を出力する.

    4. 出来事4 は「脱退」であり,店舗1, 2, 3 の待機列のうち,並んでいる客が3 人以上である店舗1, 2 の

   待機列からは先頭から3 人が去り,並んでいる客が3 人未満である店舗3 の待機列からは全員が去っ

   た.この直後,店舗1, 2, 3 の待機列はそれぞれ(2), (2, 2, 2), () となった.

    5. 出来事5 は「サービス」である.店舗1 の待機列には1 人の客がおり,これは2 人未満であるため,

   店員がデザートを食べた.したがって,0 を出力する.

    6. 出来事6 は「加入」であり,店舗2, 3 の待機列の末尾に団体4 の客が2 人ずつ加わった.この直後,

    店舗1, 2, 3 の待機列はそれぞれ(2), (2, 2, 2, 4, 4), (4, 4) となった.

    7. 出来事7 は「サービス」である.店舗3 の待機列には2 人の客がおり,これは2 人以上であるため,

   先頭から2 人目の客にデザートをおまけした.この客は団体4 に属するため,4 を出力する.

 この入出力例は小課題2, 7, 8 の制約を満たす.





                     フードコート– 4 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2021 (Komaba, Tokyo)


                                                                   Contest Day 1 – Food Court


 入力例2              出力例2

 3 4 7                          4

 1 1 2 1 1                      0

 1 1 3 4 1

 2 2 3 1

 2 1 3 1

 1 1 2 2 1

 3 1 1

 3 3 2

この入出力例は小課題1, 2, 3, 5, 7, 8 の制約を満たす.





                    フードコート– 5 / 6

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                      Spring Training Camp/Qualifying Trial

                                               March 20–23, 2021 (Komaba, Tokyo)


                                                                  Contest Day 1 – Food Court


入力例3                    出力例3

183326 218318 22                        0

1 106761 160918 151683 574906362        22166

3 68709 1                               32334

1 29240 156379 22166 957318472          0

1 14054 181502 82845 97183925           82845

2 112033 122908 587808357               8750

2 57819 160939 215041262                60918

3 36674 524274467

1 35854 69866 32334 322730299

1 1384 7230 115069 454256926

1 44192 158235 8750 84192710

3 54457 1077490708

2 10592 110384 979714505

2 44594 79244 311724477

3 160965 97183926

1 88748 101697 39148 373927458

3 41166 58039001

1 91501 137591 205480 958877326

2 77775 169655 135756956

1 12497 57047 60918 15666764

1 47839 51716 144688 732270998

3 114514 774994894

3 48645 169986425





                   フードコート– 6 / 6