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;
}