Horizon (old)

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <set>
#include <vector>

#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define pii pair<int,int>

typedef long long ll;
using namespace std;

int N;
multiset<int, greater<int> > S;
vector< pair< pii, int> > Events;

int main()
{
    cin >> N;

    f(i,1,N)
    {
        int l,r,h;
        scanf("%d %d %d", &l, &r, &h);
        Events.push_back(make_pair(make_pair(l,0),h));
        Events.push_back(make_pair(make_pair(r,1),h));
    }

    sort(Events.begin(), Events.end());

    int last = 0;
    ll ans = 0;

    for(int i = 0; i < 2*N; i++)
    {
        int x = Events[i].first.first, t = Events[i].first.second, h = Events[i].second;

        if(!S.empty())
        {
            ll h = *S.begin();
            ans += h * (x-last);
        }

        if(t==0) S.insert(h);
        else
        {
            multiset<int, greater<int> >::iterator it = S.find(h);
            S.erase(it);
        }

        last = x;
    }

    cout << ans;
}