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




可复制的 PDF 提取文本
The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
JOI Open Contest
August 5, 2023
garden
庭園(Garden)
JOI 王国は,果てしなく広がる領地を持つ不思議な王国である.国王であるJOI 君は,領地の一部を切り
取って自分の庭にしようと考えている.
JOI 王国の領地は十分に広い2 次元のグリッドとして表される.このグリッドは上下左右の方向に正方形
のマスが敷き詰められたものであり,ある基準となるマスから右方向にx 回,上方向にy 回進んだ場所にあ
るマスを(x, y) と表す.ただし,左方向にa 回進むことは,右方向に−a 回進むことと等しいものとする.
同様に,下方向にa 回進むことは,上方向に−a 回進むことと等しいものとする.領地にはいくつかの種類
のオブジェが置かれていて,これらのオブジェはその置かれ方によってタイプA とタイプB に分別される.
• タイプA のオブジェは全部でN 種類あり,i 種類目(1 ≦i ≦N) のオブジェは,(Pi + kD, Qi + lD)
(k, l は整数)と表されるようなすべてのマスに1 つずつ置かれている.
• タイプB のオブジェは全部でM 種類あり,j 種類目(1 ≦j ≦M) のオブジェは,(R j + kD, y)(k, y は
整数)と表されるか(x, S j + lD)(l, x は整数)と表されるようなすべてのマスに1 つずつ置かれて
いる.
なお,1 つのマスに複数の種類のオブジェが置かれているかもしれないことに注意せよ.
JOI 君は,グリッド上の長方形領域を1 つ選んで庭にしようと考えている.すなわち,4 つの整数a, b, c, d
を選んだ上で,a ≦x ≦b, c ≦y ≦d を満たす整数x, y を用いて(x, y) と表されるマス全体をJOI 君の庭とす
る.JOI 君はさまざまなオブジェを眺めるのが好きなので,N + M 種類あるオブジェのいずれについても,
その種類のオブジェが1 つ以上JOI 君の庭に置かれていなければならない.あまり大きい庭を作ってしま
うと国民に怒られてしまうかもしれないので,JOI 君はそのような条件の下で含まれるマスの個数ができる
だけ少ない庭を作ろうと考えている.
オブジェの情報が与えられたとき,JOI 君の庭を構成するマスの個数の最小値を求めるプログラムを作成
せよ.
庭園– 1 / 4
The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
JOI Open Contest
August 5, 2023
garden
入力
入力は以下の形式で標準入力から与えられる.
N M D
P1 Q1
P2 Q2
...
PN QN
R1 S 1
R2 S 2
...
RM S M
出力
標準出力に,JOI 君の庭を構成するマスの個数の最小値を1 行で出力せよ.
制約
• N ≧1.
• M ≧1.
• N + M ≦500 000.
• 1 ≦D ≦5 000.
• 0 ≦Pi < D (1 ≦i ≦N).
• 0 ≦Qi < D (1 ≦i ≦N).
• 0 ≦Rj < D (1 ≦j ≦M).
• 0 ≦S j < D (1 ≦j ≦M).
• 入力される値はすべて整数である.
庭園– 2 / 4
The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
JOI Open Contest
August 5, 2023
garden
小課題
1. (15 点) M ≦8.
2. (6 点) D ≦10,N + M ≦5000.
3. (8 点) D ≦50,N + M ≦5000.
4. (16 点) D ≦100,N + M ≦5000.
5. (30 点) N + M ≦5000.
6. (25 点) 追加の制約はない.
入出力例
入力例1 出力例1
2 1 5 8
1 4
2 2
0 0
JOI 王国の領地のうち,0 ≦x < 10, 0 ≦y < 10 を満たす整数x, y を用いて(x, y) と表されるマスについて
図示したものが次の図である.
庭園– 3 / 4
The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
JOI Open Contest
August 5, 2023
garden
円と菱形はそれぞれタイプA,B のオブジェを表し,中に書かれた数字はオブジェの種類を表す.
a = 1, b = 2, c = 2, d = 5 と選ぶと,JOI 君の庭は図で黒く塗られた部分になる.このとき,3 種類あるオブ
ジェのすべてが庭に置かれている.この庭を構成するマスの個数は8 であり,これより少ないマスの個数で
条件を満たす庭は存在しない.よって8 を出力する.
この入力例はすべての小課題の制約を満たす.
入力例2 出力例2
3 4 100 2840
20 26
81 56
20 3
58 71
74 82
95 61
95 61
この入力例は小課題1, 4, 5, 6 の制約を満たす.
入力例3 出力例3
5 7 5000 10543092
1046 365
4122 1166
4009 2896
1815 4065
4372 1651
2382 123
1475 836
3313 4005
2579 568
4300 4867
1050 3214
3589 4653
この入力例は小課題1, 5, 6 の制約を満たす.
庭園– 4 / 4