1465. The Heaviest Point, and How Wide the Peak Is

n weights are laid on a line. Weight i is written l r v and adds v to every point of the HALF-OPEN stretch [l, r), so the point r itself gets nothing and a weight ending at r and one starting at r never both press on a point.

Print two integers on one line: the largest total weight pressing on any point, and the total LENGTH of the set of points carrying that much.

[1,5) w 2, [2,6) w 3, [8,9) w 10, [3,4) w 1 -> 10 1 [1,3) w 5, [3,5) w 5, [5,7) w 5 -> 5 6 [0,10) w 1, [0,10) w 1, [0,10) w 1 -> 3 10

The second line is the endpoint rule and the reason the width is asked for. The three weights hand over cleanly, so the total is 5 from 1 all the way to 7, which is ONE stretch of width 6 rather than three of width 2. Under a CLOSED reading the total would reach 10 at the two handover points and the answer would be different in both numbers.

## What most people try first

An array of totals indexed by point, updated with the difference array from problem 1464. That is exactly right when the axis is small, and here l and r reach 10^9 in both directions, so the array would need 2 * 10^9 entries.

The second reflex is, for each weight, to check every other weight for overlap. That is O(n^2), 4 * 10^10 at the limits, and it answers a pairwise question rather than a pointwise one.

## The difference array with its coordinates carried along

Keep the idea and drop the positions that never change:

for each weight l r v: event(l, +v) and event(r, -v) sort the events by coordinate total = 0; best = 0; width = 0 for each consecutive pair of distinct coordinates (x, next): apply every event at x if total > best: best = total; width = next - x else if total == best: width += next - x

O(n log n) for the sort, then one pass. This is coordinate compression in its lightest form: instead of building a table of ranks, the events carry their own coordinates and the sort does the compressing.

## Why the width has to be accumulated and not measured once

The maximum total can be reached on several separate stretches, and it can also be reached on several CONSECUTIVE elementary stretches that happen to be split by a coordinate where nothing net changes. Both are summed, because the question asks for the total length of the set of points at the maximum, not for the widest single stretch.

That is the difference between this problem and problem 1461, which wants the widest single stretch and therefore has to join consecutive pieces before comparing them. Here the sum makes joining unnecessary: two pieces at the same level contribute their two widths whether or not they meet.

## The boundary that breaks a careless implementation

Resetting width when a new maximum appears, and ADDING to it when the maximum is merely equalled. Getting those two the wrong way round gives the width of the last stretch at the peak instead of the total.

The last coordinate has no gap after it, so the loop must stop there. The total is 0 at that point in any case, since every weight has been lifted.

## Overflow

2 * 10^5 weights of 10^9 stacked on one point reach 2 * 10^14, far past the 2147483647 a signed 32 bit integer holds, so the running total needs 64 bits. Two such weights reach exactly 2 * 10^9, which still FITS in a signed 32 bit integer. The WIDTH reaches 2 * 10^9 as well and also fits, though it is safest in 64 bit alongside the total.

## Related

Problem 1464 is this question over an array small enough to hold, where the difference array can be indexed directly. Problem 1450 measures how long the COUNT is at or above a level, which is this with every weight equal to 1 and the comparison loosened. Problem 1461 asks for the widest single stretch at an exact level, which needs the joining step this problem avoids.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ l < r ≤ 10^9` - `1 ≤ v ≤ 10^9`, so every weight is positive and the maximum total is at least 1 - each weight presses on the half-open stretch `[l, r)`, so the point `r` carries none of it