No.1338 Giant Class
タグ : / 解いたユーザー数 226
作問者 :
first_vil
/ テスター :
QCFium
問題文
Vil君の身長は160cmですが、その同級生は皆、身長が170km以上あります。 そのような身長の高い同級生の後ろに座ると黒板が見えないので、教室内でVil君の座れる席は限られています。
教室には縦に $H$ 行、横に $W$ 列、合計 $H \times W$ 台の机が置かれていて、初めは誰もいません。これから $Q$ 人の生徒が順に登校してきます。 前から $y$ 行目、左から $x$ 列目の机を $(y,x)$ と表すことにすると、$i$ 人目の生徒は $(Y_i,X_i)$ に座ります。
それぞれの生徒が着席した直後にVil君が座れる席の個数を求めてください。 ここで、Vil君が $(y,x)$ に座れるとはその時点で $(h,x)(1 \le h \le y)$ のいずれにも生徒が座っていないことを指します。
入力
$H\ W\ Q$ $Y_1\ X_1$ $Y_2\ X_2$ $\vdots$ $Y_Q\ X_Q$
- 入力は全て整数
- $1 \le H,W \le 10^9$
- $1 \le Q \le \min(H \times W,10^5)$
- $1 \le Y_i \le H$
- $1 \le X_i \le W$
- $i \neq j $ であれば $(Y_i,X_i) \neq (Y_j,X_j)$
出力
$Q$ 行出力してください。
$i(1 \le i \le Q)$ 行目には、$i$ 人目の生徒が着席した直後にVil君が座れる席がいくつあるかを出力し、 最後に改行してください。
サンプル
サンプル1
入力
3 3 3 1 1 2 3 3 1
出力
6 4 4
座れる席を.、座れない席を#で表します。
$1$ 人目の生徒は $(1,1)$ に座ります。この直後に座れる席は $(1,2),(1,3),(2,2),(2,3),(3,2),(3,3)$ の $6$ つです。
#.. #.. #..
$2$ 人目の生徒は $(2,3)$ に座ります。この直後に座れる席は $(1,2),(1,3),(2,2),(3,2)$ の $4$ つです。
#.. #.# #.#
$3$ 人目の生徒は $(3,1)$ に座ります。この直後に座れる席は変化しません。Vil君以外の生徒には身長による座れる席の制限が無いことに注意してください。
#.. #.# #.#
サンプル2
入力
8 9 7 4 6 6 5 2 3 3 5 5 6 2 5 1 5
出力
67 64 57 54 54 53 52
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。