Hanoi Factory
Contest: Codeforces Round 401 (Div. 2)
Difficulty rating: 2000
Tags: brute force, data structures, dp, greedy, sortings

Of course you have heard the famous task about Hanoi Towers, but did you know that there is a special factory producing the rings for this wonderful game? Once upon a time, the ruler of the ancient Egypt ordered the workers of Hanoi Factory to create as high tower as possible. They were not ready to serve such a strange order so they had to create this new tower using already produced rings.

There are n rings in factory's stock. The i-th ring has inner radius ai, outer radius bi and height hi. The goal is to select some subset of rings and arrange them such that the following conditions are satisfied:

- Outer radiuses form a non-increasing sequence, i.e. one can put the j-th ring on the i-th ring only if bj ≤ bi.
- Rings should not fall one into the the other. That means one can place ring j on the ring i only if bj > ai.
- The total height of all rings used should be maximum possible.

Input format:
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of rings in factory's stock.

The i-th of the next n lines contains three integers ai, bi and hi (1 ≤ ai, bi, hi ≤ 109, bi > ai) — inner radius, outer radius and the height of the i-th ring respectively.

Output format:
Print one integer — the maximum height of the tower that can be obtained.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample, the optimal solution is to take all the rings and put them on each other in order 3, 2, 1.

In the second sample, one can put the ring 3 on the ring 4 and get the tower of height 3, or put the ring 1 on the ring 2 and get the tower of height 4.

Example input:
3
1 5 1
2 6 2
3 7 3

Example output:
6

Example input:
4
1 2 1
1 3 3
4 6 2
5 7 1

Example output:
4

Editorial:
To start with make the following observation: if two rings i and j have equal outer radiuses bi = bj they can be merged in one ring of the same outer radius, inner radius equal to min(ai, aj) and height equal to hi + hj.
Using the observation we transform our problem to the one with distinct outer radiuses. Sort ring by this radius in descending order. From this point we consider bi < bj for all i > j. For each ring we want to compute value ans(i) — maximum height of the tower that ends with the ring i. This dynamic programming can be computed in O(n2) time using the following formula: $$$$.
There are two different ways to speed up the calculation of this dp:
1. Keep rings sorted by inner radius in a separate array. For each ring j < i store its value of ans(j) there and 0 for others. To get max ans(j) we have to query maximum on some suffix of this array: from the one hand only rings with original index j < i will be non-zero, from the other hand this will suffice the condition bi > aj. This can be done using segment tree or binary indexed tree.
2. Note that if i < j < k and it's possible to place ring k on ring j and ring k on ring i, then it's possible to place ring j on ring i. Indeed, from ai < bk and bk < bj follows ai < bj. That means we only need to compute for each i maximum value j such that aj < bi. This can be done using data structures listed above or just with a single pass over array with a stack. Go from left to right and keep indexes of all valid positions in increasing order. Pop elements while they do not suffice condition aj < ai and then put i on the top. For clarifications, check the following code: stack <int> opt;for (int i = 0; i < n; i++) {     while (!opt.empty() && r[opt.back()].inner >= r[i].outer)         opt.pop();     if (!opt.empty())         ans[i] = ans[opt.back()];     ans[i] += r[i].height;     opt.push(i);}