E： たい焼きマスターと食べ盛り - Taiyaki-Master and Eater

物語

つたさんはたい焼きを作るのがとても上手い。えびちゃんはそんなつたさんが作るたい焼きが大好きだ。　2 人は毎週たい焼きを作って食べて幸せに過ごしているが、たい焼きを作っているそばで食べ盛りのえびちゃんにつまみ食いをされてしまうのがつたさんの最近の悩みだ。

学校祭でたい焼きを作ることになったつたさんは、いつものようにえびちゃんにつまみ食いされていたら売上が心配なので、自分が注目している範囲のたい焼きの様子を知ることができればいいなと思った。学校祭が成功するように、つたさんを助けてあげよう。

問題

縦 H、横 W の長方形状のたい焼きプレートがあり、たい焼きをセットしてから焼き上がるまでに T 分かかる。このプレートはたい焼きを一度に最大 HW 個焼くことができ、プレートの上から i (1≤i≤H) 番目で左から j (1≤j≤W) 番目の場所で焼いているたい焼きは (i,j) で表される。

次の 3 種類のイベントが合計 Q 回発生する。なお、初期状態ではたい焼きはいずれの場所にもセットされていない。

• 時刻 t につたさんが (h,w) にたい焼きを 1 つセットする。そのたい焼きは T 分で焼き上がり、時刻 t+T の時点で食べることができるようになる。ただし、すでにたい焼きがセットされている場所にたい焼きをセットすることはない。
• 時刻 t に、えびちゃんが (h,w) にあるたい焼きをつまみ食いしようとする。ただし、つまみ食いできるのはすでに焼き上がったたい焼きのみである。つまみ食いした後はその場所からたい焼きが無くなる (すなわち、たい焼きがセットされていない状態になる)。たい焼きが焼き上がっていない、またはたい焼きがない場所にもつまみ食いのイベントが発生する場合があることに注意せよ。
• 左上が (h₁,w₁)、右下が (h₂,w₂) となるような長方形領域内 ((h₁,w₁) および (h₂,w₂) を含む) のたい焼きについて、次の数が時刻 t の時点でそれぞれいくつであるかをつたさんがカウントする。
• すでに焼き上がったたい焼きの数
• まだ焼き上がっていないたい焼きの数

入力形式

H W T Q  
t1 c1 h11 w11 (h12 w12)
t2 c2 h21 w21 (h22 w22)
…
tQ cQ hQ1 wQ1 (hQ2 wQ2)

入力は全て整数で与えられる。

1 行目には、たい焼きプレートの縦 H、 横 W、 たい焼きをセットしてから焼きあがるまでの時間 T、 イベントの数 Q が与えられる。

1+i (1≤i≤Q) 行目には、時刻 t_i で発生したイベントの内容が与えられる。

• c_i はイベントの種類を表す。この値が 0 ならばたい焼きをセットするイベント、 1 ならばつまみ食いをするイベント、 2 ならばたい焼きをカウントするイベントを指す。
• h_i1 (1≤h_i1≤H)、w_i1 (1≤w_i1≤W) は、c_i=0,1 において次のような意味である。
• c_i=0 のとき、(h_i1,w_i1) の場所にたい焼きを1つセットする。
• c_i=1 のとき、(h_i1,w_i1) の場所に焼き上がった状態のたい焼きがあればつまみ食いをし、そうでなければ何もしない。
• h_i2、w_i2 は、c_i=2 のときのみ与えられる。
• c_i=2 のとき、左上を (h_i1,w_i1)、 右下を (h_i2,w_i2) とする長方形領域内のたい焼きについてカウントする。

入出力が非常に多くなることが予想されるため、入出力に遅い関数を使っている場合は注意してください。

制約

• 1≤H≤2×10³
• 1≤W≤2×10³
• 1≤T≤10⁹
• 1≤Q≤10⁵
• 1≤t_i≤10⁹
• i<j ならば、 t_i<t_j
• 0≤c_i≤2
• 1≤h_i1≤h_i2≤H
• 1≤w_i1≤w_i2≤W

出力形式

(c_i=2 (1≤i≤Q) の個数) を n とする。たい焼きのカウントの結果を、次の書き方に従ってイベントの発生時間が早い順に n 行に出力せよ。

a1 b1  
a2 b2  
…  
an bn

• a_i は、領域内にある「焼き上がったたい焼きの数」である。
• b_i は、領域内にある「まだ焼き上がっていないたい焼きの数」である。
• 末尾の改行を忘れないこと。

入力例1

3 3 3 6
1 0 1 1
2 2 1 1 2 2
3 1 1 1
4 0 2 1
5 2 1 1 2 2
6 2 2 1 3 3

出力例1

0 1
1 1
0 1

この入出力例では以下のイベントが発生している。

• 時刻 1 分に、(1,1) にたい焼きをセットする。このたい焼きは時刻 4 分に焼き上がる。

• 時刻 2 分に、左上 (1,1)、右下 (2,2) の長方形領域にあるたい焼きをカウントする。(1,1) にセットしたたい焼きはまだ焼き上がっていないため、0 1 を出力する。

• 時刻 3 分に、(1,1) にあるたい焼きをつまみ食いしようとするが、まだ焼き上がっていないので何もしない。

• 時刻 4 分に、(2,1) にたい焼きをセットする。このたい焼きは時刻 7 分に焼き上がる。

• 時刻 5 分に、左上 (1,1)、右下 (2,2) の長方形領域にあるたい焼きをカウントする。(1,1) のたい焼きは焼き上がっており、 (2,1) のたい焼きはまだ焼き上がっていないため、1 1 を出力する。

• 時刻 6 分に、左上 (2,1)、右下 (3,3) の長方形領域にあるたい焼きをカウントする。(2,1) のたい焼きはまだ焼き上がっていないため、0 1 を出力する。

Note

Link

 

---