Adding New Machine (ZOJ Problem Set - 3540)

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

問題

W*Hの場所にn個長方形の古いマシンがある。そこに1*mの新しいマシンを置きたいのだが置ける場所は何通りある？
1<=W,H<=10^7
0<=n<=50000
1<=m<=1000
古いマシンは重なっていない。

解法

平面走査。ならし計算量で考えるとO(nlogn)になる。m=1の場合に注意。