Draw a Mess (ZOJ Problem Set - 3544)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3544

問題

n*mのマスに順番にq個の図形が書かれていった。既に色が塗られいた場所に後から色塗ると上書きされる。最後の状態で各色のセルは何マスあるか答えよ。
1<=n<=200
1<=m<=50000
1<=q<=50000

解法

長さが短い方を縦として考えて、図形を書いていった時に各行でどのx座標から色を塗り始めてどこで塗り終えたかを前処理で計算しておく。
その後各行ごとにpriority_queueとかを使って一番上にある色を管理しながら色を塗れば良い。
三角形の塗り方がよう分からんのでwatashiさんのブログを参考にした。