Choose a Square
Contest: Educational Codeforces Round 73 (Rated for Div. 2)
Difficulty rating: 2400
Tags: binary search, data structures, sortings

Petya recently found a game "Choose a Square". In this game, there are $$$n$$$ points numbered from $$$1$$$ to $$$n$$$ on an infinite field. The $$$i$$$-th point has coordinates $$$(x_i, y_i)$$$ and cost $$$c_i$$$.

You have to choose a square such that its sides are parallel to coordinate axes, the lower left and upper right corners belong to the line $$$y = x$$$, and all corners have integer coordinates.

The score you get is the sum of costs of the points covered by the selected square minus the length of the side of the square. Note that the length of the side can be zero.

Petya asks you to calculate the maximum possible score in the game that can be achieved by placing exactly one square.

Input format:
The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the number of points on the field.

Each of the following $$$n$$$ lines contains three integers $$$x_i, y_i, c_i$$$ ($$$0 \le x_i, y_i \le 10^9, -10^6 \le c_i \le 10^6$$$) — coordinates of the $$$i$$$-th point and its cost, respectively.

Output format:
In the first line print the maximum score Petya can achieve.

In the second line print four integers $$$x_1, y_1, x_2, y_2$$$ ($$$0 \le x_1, y_1, x_2, y_2 \le 2 \cdot 10^9, x_1 = y_1, x_2 = y_2, x_1 \le x_2$$$) separated by spaces — the coordinates of the lower left and upper right corners of the square which Petya has to select in order to achieve the maximum score.

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

Note:
The field corresponding to the first example:

Example input:
6
0 0 2
1 0 -5
1 1 3
2 3 4
1 4 -4
3 1 -1

Example output:
4
1 1 3 3

Example input:
5
3 3 0
3 3 -3
0 2 -1
3 1 3
0 0 -2

Example output:
0
1 1 1 1

Editorial:
Notice that the square ($$$l, l$$$) ($$$r, r$$$) covers the point ($$$x, y$$$) if and only if $$$l \le min(x, y) \le max(x, y) \le r$$$.
Using this fact, let's reformulate the problem the following way: we have to find the segment $$$(l, r)$$$, such that the sum of the segments fully covered by it is maximal.
Let's build a segment tree, the $$$r$$$-th of its leaves stores $$$f(l, r)$$$ — the sum of the segments covered by the segment $$$(l, r)$$$ . Initially, it's built for some $$$l$$$ such that it is to the right of all segments. Other nodes store the maximum in them.
Now let's iterate over the values ​​of $$$l$$$ in descending order. Let there be some segment starting in $$$l$$$ $$$(l, x)$$$ with the cost $$$c$$$. All the answers $$$f(l, r)$$$ for $$$r < x$$$ won't change because they don't cover that new segment. And the values on the suffix from the position $$$x$$$ ($$$r \ge x$$$) will increase by $$$c$$$.
The only thing left is to learn how to handle the subtraction of the length of the side. That term is $$$(r - l)$$$ and the thing we are looking for is $$$\max \limits_{r} f(l, r) - (r - l)$$$. Rewrite it in form $$$l + \max \limits_{r} f(l, r) - r$$$ and you'll see that you can just subtract $$$r$$$ from the value of the $$$r$$$-th leaf of the segment tree at the beginning to get the correct result. Surely, you'll need to add that $$$l$$$ after you ask the maximum of all the segtree to obtain the answer.
You'll probably need to compress the coordinates — leave only such positions $$$i$$$ that there is at least one $$$x = i$$$ or $$$y = i$$$. Implicit segtree might work but neither ML, nor TL are not friendly to it. Also be careful with the case with all points being negative.