問題概要
問題ページ
-
-
C - Reorder Cards
問題ページへ移動する
問題文
\(H\) 行 \(W\) 列の格子状に \(HW\) 枚のカードが並べられています。
\(i=1,\ldots,N\) について、上から \(A_i\) 行目、左から \(B_i\) 列目にあるカードには数 \(i\) が書かれており、それ以外の \(HW-N\) 枚のカードには何も書かれていません。
これらのカードに対し、以下の \(2\) 種類の操作を可能な限り繰り返します。
- 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
- 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める
操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。
制約
- \(1 \leq H,W \leq 10^9\)
- \(1 \leq N \leq \min(10^5,HW)\)
- \(1 \leq A_i \leq H\)
- \(1 \leq B_i \leq W\)
- \((A_i,B_i)\) は相異なる
- 入力に含まれる値は全て整数である
問題の考察
ACコード
import sys
import collections
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
h, w, n = list(map(int, input().rstrip('\n').split()))
ad = collections.defaultdict(int)
bd = collections.defaultdict(int)
ab = []
for i in range(n):
a, b = list(map(int, input().rstrip('\n').split()))
ab.append([a, b])
ad[a], bd[b]
al = 0
ac = 0
for k in sorted(ad.keys()):
ac += k - al - 1
al = k
ad[k] = ac
bl = 0
bc = 0
for k in sorted(bd.keys()):
bc += k - bl - 1
bl = k
bd[k] = bc
for a, b in ab:
print(a - ad[a], b - bd[b])
if __name__ == '__main__':
solve()