← 返回题目列表

AtCoder · joisc2020_c

C. 扫地

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

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

掃除 (Sweeping) - 原题 PDF 第 1 页
原题PDF第1页
掃除 (Sweeping) - 原题 PDF 第 2 页
原题PDF第2页
掃除 (Sweeping) - 原题 PDF 第 3 页
原题PDF第3页
掃除 (Sweeping) - 原题 PDF 第 4 页
原题PDF第4页
掃除 (Sweeping) - 原题 PDF 第 5 页
原题PDF第5页
掃除 (Sweeping) - 原题 PDF 第 6 页
原题PDF第6页
掃除 (Sweeping) - 原题 PDF 第 7 页
原题PDF第7页
掃除 (Sweeping) - 原题 PDF 第 8 页
原题PDF第8页
掃除 (Sweeping) - 原题 PDF 第 9 页
原题PDF第9页
可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                       Contest Day 1 – Sweeping

                     掃除(Sweeping)



 ビ太郎は短辺の長さがN の直角二等辺三角形の部屋に住んでいる.この部屋の中のある1 点の座標は,

直角になっている部屋の隅を原点,そこから出ている片方の壁をx 軸,もう片方の壁をy 軸として(x, y) で

表される(0 ≦x ≦N,0 ≦y ≦N,x + y ≦N) .


                       (0, N)





                        (0, 0)                    (N, 0)



 ある日,ビ太郎は自分の部屋にホコリが溜まっていることを感じた.ホコリは最初の時点でM 個あり,i
番目(1 ≦i ≦M) のホコリは座標(Xi, Yi) にある.同じ座標に2 個以上のホコリがあるかもしれない.

 ビ太郎はほうきを使った掃き掃除をすることにした.ほうきの接地面は線分であり,その長さをほうきの

幅と呼ぶ.ビ太郎は几帳面なので,以下の2 通りの方法でしかほうきを動かさない.

    • ほうきの片方の端が原点に来るようにy 軸の壁に沿ってほうきを置く.その後,y 軸の壁と平行に,

   片方の端をx 軸の壁と接触させたまま,x 軸の正の方向にほうきを動かせるだけ動かす.幅l のほう

    きを使うとき,(x, y) にあったホコリは,x < N −l かつy ≦l を満たすならば(N −l, y) へと移動する

   (移動した先に別のホコリがあるかもしれない).この動かし方を手順H とする.

    • ほうきの片方の端が原点に来るようにx 軸の壁に沿ってほうきを置く.その後,x 軸の壁と平行に,

   片方の端をy 軸の壁に接触させたまま,y 軸の正の方向にほうきを動かせるだけ動かす.幅l のほう

    きを使うとき,(x, y) にあったホコリは,x ≦l かつy < N −l を満たすならば(x, N −l) へと移動する

   (移動した先に別のホコリがあるかもしれない).この動かし方を手順V とする.

 この部屋ではこれからQ 個のイベントが連続して起こる.j 番目(1 ≦j ≦Q) のイベントは以下のいずれ

かである.




                          掃除– 1 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                       Contest Day 1 – Sweeping


    • ビ太郎がPj 番目のホコリの座標を求める.
    • ビ太郎が幅L j のほうきを使い,手順H を行う.
    • ビ太郎が幅L j のほうきを使い,手順V を行う.
    • 新たなホコリが(Aj, Bj) に追加される.そのホコリが追加される前に存在していたホコリの数がc で
   あるとき,そのホコリはc + 1 番目のホコリとなる.

 部屋の短辺の幅,もともとあったホコリの座標,イベントの内容が与えられたとき,ホコリの位置を求め

るプログラムを作成せよ.


入力


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


    N M Q

      X1 Y1
                                 ...

     XM YM

      (Query 1)
                                 ...

      (Query Q)

 ただし,各(Query j) (1 ≦j ≦Q) には2 個または3 個の整数が空白を区切りとして書かれている.1 個目
の整数をT j とすると,この行の内容は以下のいずれかである.

    • T j = 1 のとき.この行には2 個の整数T j, Pj がこの順に書かれている.これはj 番目のイベントが,
   ビ太郎がPj 番目のホコリの座標を求めるものであることを表す.
    • T j = 2 のとき.この行には2 個の整数T j, L j がこの順に書かれている.これはj 番目のイベントが,
   ビ太郎が幅L j のほうきを使い,手順H を行うものであることを表す.
    • T j = 3 のとき.この行には2 個の整数T j, L j がこの順に書かれている.これはj 番目のイベントが,
   ビ太郎が幅L j のほうきを使い,手順V を行うものであることを表す.
    • T j = 4 のとき.この行には3 個の整数T j, A j, Bj がこの順に書かれている.これはj 番目のイベント
    が,新たなホコリが(Aj, Bj) に追加されるものであることを表す.





                          掃除– 2 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                       Contest Day 1 – Sweeping



出力

 標準出力に,T j = 1 となるイベントのそれぞれに対して,j 個目のイベントの時点でのホコリPj のx 座
標,y 座標を空白区切りで1 行で出力せよ.


制約

    • 1 ≦N ≦1 000 000 000.

    • 1 ≦M ≦500 000.

    • 1 ≦Q ≦1 000 000.
    • 0 ≦Xi ≦N (1 ≦i ≦M).
    • 0 ≦Yi ≦N (1 ≦i ≦M).
    • Xi + Yi ≦N (1 ≦i ≦M).
    • 1 ≦Pj ≦(その時点でのホコリの数) (1 ≦j ≦Q).
    • 0 ≦L j ≦N −1 (1 ≦j ≦Q).
    • 0 ≦Aj ≦N (1 ≦j ≦Q).
    • 0 ≦Bj ≦N (1 ≦j ≦Q).
    • Aj + Bj ≦N (1 ≦j ≦Q).
    • T j = 1 (1 ≦j ≦Q) となるイベントが1 個以上存在する.


小課題

    1. (1 点) M ≦2 000,Q ≦5 000.
    2. (10 点) T j = 1, 2, 4.
    3. (11 点) T j = 1, 2, 3,X j ≦Xj+1,Y j ≧Y j+1 (1 ≦j ≦M −1).
    4. (53 点) T j = 1, 2, 3.
    5. (25 点) 追加の制約はない.





                          掃除– 3 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                       Contest Day 1 – Sweeping



入出力例

  入力例1              出力例1

   6 2 10                         1 3

   1 1                            3 2

   4 0                            3 3

   4 2 3                          6 0

   3 3

   1 1

   4 1 2

   2 3

   2 0

   1 4

   3 2

   1 3

   1 2


    • 最初,1 番目のホコリが(1, 1),2 番目のホコリが(4, 0) に存在している.図1 はこのときの部屋の様

   子を表している.

    • 1 番目のイベントでは,3 番目のホコリが(2, 3) に追加される.図2 はこのときの部屋の様子を表し

   ている.

    • 2 番目のイベントでは,幅3 のほうきを使って手順V を行う.その結果,1 番目のホコリが(1, 3) に

   移動する.図3 はこのときの部屋の様子を表している.

    • 3 番目のイベントでは,1 番目のホコリの座標(1, 3) を求める.

    • 4 番目のイベントでは,4 番目のホコリが(1, 2) に追加される.図4 はこのときの部屋の様子を表し

   ている.

    • 5 番目のイベントでは,幅3 のほうきを使って手順H を行う.その結果,1 番目のホコリが(3, 3),3

   番目のホコリが(3, 3),4 番目のホコリが(3, 2) に移動する.図5 はこのときの部屋の様子を表して

   いる.

    • 6 番目のイベントでは,幅0 のほうきを使って手順H を行う.その結果,2 番目のホコリが(6, 0) に

   移動する.図6 はこのときの部屋の様子を表している.

    • 7 番目のイベントでは,4 番目のホコリの座標(3, 2) を求める.

    • 8 番目のイベントでは,幅2 のほうきを使って手順V を行う.その結果,どのホコリも移動しない.

   図7 はこのときの部屋の様子を表している.



                          掃除– 4 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2020 (Komaba, Tokyo)


                                                                     Contest Day 1 – Sweeping


  • 9 番目のイベントでは,3 番目のホコリの座標(3, 3) を求める.

  • 10 番目のイベントでは,2 番目のホコリの座標(6, 0) を求める.

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





           図1                        図2





           図3                        図4





                        掃除– 5 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                    Spring Training Camp/Qualifying Trial

                                March 20–23, 2020 (Komaba, Tokyo)


                                                  Contest Day 1 – Sweeping





図5                        図6





図7





             掃除– 6 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2020 (Komaba, Tokyo)


                                                                     Contest Day 1 – Sweeping


 入力例2              出力例2

 9 4 8                          3 6

 2 3                            4 3

 3 1                            7 1

 1 6                            6 3

 4 3

 2 6

 1 3

 2 2

 1 4

 2 3

 1 2

 2 4

 1 1

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


 入力例3              出力例3

 8 1 8                          4 1

 1 5                            3 5

 4 4 1                          3 2

 2 6

 1 2

 2 3

 4 2 2

 2 5

 1 1

 1 3

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





                        掃除– 7 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2020 (Komaba, Tokyo)


                                                                     Contest Day 1 – Sweeping


 入力例4              出力例4

 7 4 9                          4 2

 1 5                            5 1

 2 2                            1 6

 4 2                            5 2

 5 0

 2 6

 2 3

 1 2

 3 6

 1 4

 3 1

 1 1

 2 2

 1 3

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





                        掃除– 8 / 9

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2020 (Komaba, Tokyo)


                                                                     Contest Day 1 – Sweeping


 入力例5              出力例5

 20 5 25                        2 17

 10 6                           2 17

 0 4                            9 8

 2 1                            0 17

 1 0                            1 17

 2 3                            3 3

 2 18                           10 10

 3 9                            2 17

 4 1 5                          2 17

 4 0 2                          0 17

 3 10

 4 3 3

 3 3

 2 9

 4 9 1

 3 12

 1 4

 3 19

 1 3

 1 9

 2 1

 1 7

 1 6

 4 3 3

 1 10

 1 1

 1 5

 2 0

 1 2

 2 2

 1 7

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





                        掃除– 9 / 9