City Horizon#7747

City Horizon (Editorial)

Consider all points — the $x$ -coordinates of the beginnings and ends of the buildings — and sort them in increasing order. For each such point, we store:

its coordinate,
its type (start of a building — $t y p e = 0$ type = 0, end — $t y p e = 1$ type = 1),
the height of the corresponding building.

Next, process these points sequentially from left to right.

We maintain a multiset $s$ that stores the heights of buildings that have already started but have not yet ended at the current moment. This multiset allows us to efficiently determine the maximum height among the active buildings.

Let the current point have coordinate $x_{i}$ x_i, and the next point $x_{i + 1}$ x_{i+1}. Let $h$ denote the maximum element in the multiset $s$ (if the set is empty, assume $h = 0$ h = 0). Then, on the interval $[x_{i}, x_{i + 1}]$ [x_i, x_{i+1}]), the maximum height of the silhouette is $h$ , and the contribution to the area is

(x_{i + 1} - x_{i}) \cdot h

(x_{i+1} - x_i) \cdot h

Add this value to the total area.

After that, update the multiset:

if the point $x_{i}$ x_i is the start of a building, insert its height into $s$ ;
if it is the end of a building, we remove the corresponding height from $s$ .

The order of processing events with the same $x$ -coordinate (starts and ends of buildings) does not affect the correctness of the solution, since segments of zero length do not contribute to the area.

Example

Algorithm implementation

To represent a point, we introduce a structure $n o d e$ that stores its $x$ -coordinate, a flag indicating whether it is the start ( $t y p e = 0$ type = 0) or the end ( $t y p e = 1$ type = 1) of a segment, and the height $h$ of the corresponding building.

struct node
{
  int x, type, h;
  node(int x, int type, int h) : x(x), type(type), h(h) {};
};

Define a comparator f for points — sort them in increasing order of their $x$ -coordinates.

int f(node a, node b)
{
  return a.x < b.x;
}

Declare an array of points $E v e n t$ , as well as a multiset $s$ to store the heights of buildings intersecting the current position of the sweep line.

vector<node> Event;
multiset<int, greater<int> > s;

Read the input data. Construct the array of points.

scanf("%d",&n);
for(i = 0; i < n; i++)
{
  scanf("%d %d %d",&left,&right,&height);
  Event.push_back(node(left,0,height));
  Event.push_back(node(right,1,height));
}

C++

Sort the array of points in non-decreasing order of their $x$ -coordinates.

sort(Event.begin(),Event.end(),f);

Accumulate the total area of the city skyline in the variable $r es$ .

res = 0;

Move from left to right over the points in the $E v e n t$ array. For each index $i$ in the $f or$ loop, consider the interval $(E v e n t [i] . x, E v e n t [i + 1] . x)$ (Event[i].x, Event[i + 1].x).

for (i = 0; i < Event.size() - 1; i++)
{

If the point $x_{i}$ x_i is the start of a building, insert the corresponding height into the multiset.

  int h = Event[i].h;
  if (Event[i].type == 0) s.insert(h);

If the point $x_{i}$ x_i is the end of a building, remove the corresponding height from the multiset.

  else s.erase(s.find(h));

If the multiset is not empty, then on the segment between $E v e n t [i] . x$ Event[i].x and $E v e n t [i + 1] . x$ Event[i + 1].x there exists a skyline whose height is equal to the maximum element in $s$ , i.e. $* s . b e g in ()$ *s.begin().

  if (!s.empty())
    res += 1LL * *s.begin() * (Event[i+1].x - Event[i].x);
}

Print the computed area.

printf("%lld\n",res);

Algorithm implementation – segment tree

Perform coordinate compression of the buildings' $x$ -coordinates using a mapping $m p$ (for example, $m p [2] = 1$ mp[2] = 1, $m p [4] = 2$ mp[4] = 2 and so on). Then build a segment tree over the range $[1.. l e n]$ , where $l e n \leq 40000$ len \le 40000.

Each leaf of the segment tree corresponds to a single elementary (indivisible) interval of the skyline on the horizon. For example, node $1$ corresponds to the interval $[2; 4]$ , and node $2$ corresponds to $[4; 5]$ . Then, a segment $[a, b]$ is covered by the segment tree nodes with indices $[m p [a], m p [b] - 1]$ [mp[a], mp[b] - 1]. For example, the segment $[2; 5]$ is covered by the nodes $[m p [2], m p [5] - 1] = [1, 2]$ [mp[2], mp[5] - 1] = [1, 2].

For each building on the interval $[a_{i}, b_{i}]$ [a_i, b_i] with height $h_{i}$ h_i, increase the values in the segment tree over the interval $[m p [a_{i}], m p [b_{i}] - 1]$ [mp[a_i], mp[b_i] - 1]. While propagating values in the tree nodes, we maintain the maximum:

Push all values from the internal nodes down to the leaves, after which the leaves will store the heights of the skyline on the corresponding intervals. For example, the first leaf corresponds to the interval $[2; 4]$ and contains the value $1$ , the second leaf corresponds to $[4; 5]$ and contains the value $3$ , and so on. The last node of the segment tree does not correspond to any interval and is considered a dummy node.

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#define MAX 80010
using namespace std;

int SegTree[4*MAX];
vector<int> a;
map<int,int> mp;
int i, n, l, r, h, len;
long long res;
struct Building
{
  int left, right, height;
} b[40010];

void Push(int Vertex, int LeftPos, int Middle, int RightPos)
{
  if (SegTree[Vertex])
  {
    SegTree[2*Vertex] = max(SegTree[2*Vertex],SegTree[Vertex]);
    SegTree[2*Vertex+1] = max(SegTree[2*Vertex+1],SegTree[Vertex]);
    SegTree[Vertex] = 0;
  }
}

void Add(int Vertex, int LeftPos, int RightPos, 
         int Left, int Right, int x)
{
  if (Left > Right) return;
  if ((LeftPos == Left) && (RightPos == Right))
    SegTree[Vertex] = max(SegTree[Vertex],x);
  else
  {
    int Middle = (LeftPos + RightPos) / 2;
    Push(Vertex,LeftPos,Middle,RightPos);

    Add(2*Vertex, LeftPos, Middle, Left, min(Middle,Right), x);
    Add(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right, x);
  }
}

long long Count(int Vertex, int LeftPos, int RightPos) 
{
  if (LeftPos == RightPos) 
    return 1LL * SegTree[Vertex] * (a[LeftPos+1] - a[LeftPos]);
  else 
  {
    int Middle = (LeftPos + RightPos) / 2;
    Push(Vertex,LeftPos,Middle,RightPos);

    return Count(2*Vertex, LeftPos, Middle) +
           Count(2*Vertex+1, Middle+1, RightPos);
  }
}

int main(void)
{
  scanf("%d",&n);
  memset(SegTree,0,sizeof(SegTree));
  set<int> s;
  for(i = 1; i <= n; i++)
  {
    scanf("%d %d %d",&b[i].left,&b[i].right,&b[i].height);
    s.insert(b[i].left); s.insert(b[i].right);
  }
  len = s.size(); a.resize(len+2);
  copy(s.begin(),s.end(),a.begin()+1);
  for(i = 1; i <= len; i++) mp[a[i]] = i;

  for(i = 1; i <= n; i++)
    Add(1,1,len,mp[b[i].left],mp[b[i].right]-1,b[i].height);

  res = Count(1,1,len);
  printf("%lld\n",res);
  return 0;
}

C++