7747. City Horizon

Farmer John has arrived in the city with his cows! During sunset, the cows look at the city skyline and observe beautiful silhouettes formed by rectangular buildings.

The entire skyline is represented by a number line with n buildings. The silhouette of the i-th building extends along the horizon between points a_i and b_i and has height h_i. Determine the total area (in square units) of the silhouette formed by all n buildings.

Input. The first line contains an integer n (1 ≤ n ≤ 40000). Each of the next n lines describes the i-th building with three integers: a_i, b_i (1 ≤ a_i < b_i ≤ 10⁹) and h_i (1 ≤ h_i ≤ 10⁹).

Output. Print the total area of the city skyline (in square units) formed by all n buildings.

Sample input	Sample output
4 2 5 1 9 10 4 6 8 2 4 6 3	16

SOLUTION

sweeping line

Algorithm analysis

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 – type = 0, end – 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, and the next point x_i+1. Let h denote the maximum element in the multiset s (if the set is empty, assume h = 0). Then, on the interval [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) * h

Add this value to the total area.

After that, update the multiset:

· if the point 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 node that stores its x-coordinate, a flag indicating whether it is the start (type = 0) or the end (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 Event, 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));

}

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 res.

res = 0;

Move from left to right over the points in the Event array. For each index i in the for loop, consider the interval (Event[i].x, Event[i + 1].x).

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

{

If the point 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 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 Event[i].x and Event[i + 1].x there exists a skyline whose height is equal to the maximum element in s, i.e. *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 mp (for example, mp[2] = 1, mp[4] = 2 and so on). Then build a segment tree over the range [1..len], where len ≤ 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 [mp[a], mp[b] – 1]. For example, the segment [2; 5] is covered by the nodes [mp[2], mp[5] – 1] = [1, 2].

For each building on the interval [a_i, b_i] with height h_i, increase the values in the segment tree over the interval [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;

}