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









可复制的 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