POJ 3277 City Horizon
問題
平面上に、N個の長方形の建物がある。
建物の一辺はx軸上にある。
建物の上の辺は二点(A[i],H[i]),(B[i],H[i])を結んでいる。
建物一つ以上に覆われている領域の面積の総和を求めよ。
制約条件
N≦40000
A[i],B[i],H[i]≦10^9
方針
建物の終端の座標および高さを表す二つのpriority_queueを使う。
建物のはじまりが来たら、終端を表すキューにその建物を入れる。
そこまでの長方形の面積を答えに足す。
終端が来たら、そこまでの長方形の面積を答えに足す。
その長方形に使用済のフラグを立てる。
高さのキュー(高い順に並んでいる)から、先頭が使用済の建物の間要素を捨てる。
残っている要素が次からの高さになる。
これを繰り返せばよい。
priority_queueに要素はN回挿入、削除が行われるので、
全体の計算量はO(N log N)であり、制限時間に間に合う。
ソースコード
int N; pair<int,pi> b[40000]; bool use[40000]; int main(){ scanf("%d",&N); rep(i,N)scanf("%d%d%d",&b[i].first,&b[i].second.first,&b[i].second.second); sort(b,b+N); priority_queue<pi> height, right; int h=0, prev=0; ll ans=0; rep(i,N){ while(!right.empty() && -right.top().first<=b[i].first){ ans+=h*ll(-right.top().first-prev); prev=-right.top().first; use[right.top().second]=1; right.pop(); while(!height.empty()&&use[height.top().second])height.pop(); h=height.empty()?0:height.top().first; } ans+=h*ll(b[i].first-prev); right.push(make_pair(-b[i].second.first,i)); height.push(make_pair(b[i].second.second,i)); h=max(h,height.top().first); prev=b[i].first; } while(!right.empty()){ ans+=h*ll(-right.top().first-prev); prev=-right.top().first; use[right.top().second]=1; right.pop(); while(!height.empty()&&use[height.top().second])height.pop(); h=height.empty()?0:height.top().first; } printf("%lld\n",ans); return 0; }