Overview

Each radio tower can be thought of as adding strength \(C_i\) to the integer coordinate interval \([X_i-L_i,\;X_i+R_i]\). In other words, this problem asks: “Given many weighted intervals, at which integer coordinate is the total weight maximized?”

Analysis

The range covered by tower \(i\)’s signal, in terms of integer coordinates, is the closed interval

\[ [X_i-L_i,\;X_i+R_i] \]

You receive strength \(C_i\) only when you are within this interval.

Therefore, the received signal strength at coordinate \(p\) is:

• The sum of all \(C_i\) for intervals that contain \(p\).

Why a naive approach is difficult

For example, if we consider trying every integer coordinate in order and checking all towers for each one:

• The coordinate range can be on the order of \(10^9\)
• Moreover, coordinates can be negative

So iterating over all coordinates is impossible.

Also, even if you think “we only need to check the endpoints of each tower,” checking all towers for each candidate point would be \(O(N^2)\), which is too slow for \(N \le 10^5\).

Key insight

The total received strength does not change every time you move from one coordinate to the next. The value only changes at:

• The left endpoint of an interval, when that tower’s strength is added
• Just after passing the right endpoint of an interval, when that tower’s strength is removed

The operation of adding strength \(C\) to interval \([l, r]\) can be expressed as a difference:

• \(+C\) at \(l\)
• \(-C\) at \(r+1\)

This is the same idea as the “imos method” (prefix sum difference technique) on integer coordinates.

Concrete example

For example, suppose there are the following two towers:

• Add \(+3\) to interval \([2,5]\)
• Add \(+5\) to interval \([4,6]\)

The difference events are:

• \(+3\) at \(2\)
• \(-3\) at \(6\) (since it’s the position after \(5\), i.e., \(5+1=6\))
• \(+5\) at \(4\)
• \(-5\) at \(7\)

Processing these from left to right:

• At \(x=2\), total is \(3\)
• At \(x=4\), total is \(8\)
• At \(x=6\), total is \(5\)
• At \(x=7\), total is \(0\)

The maximum value is \(8\). Indeed, at coordinates \(4\) and \(5\), both towers are received, giving \(3+5=8\).

Why large coordinates are not a problem

The standard imos method requires an array, but in this problem coordinates can be up to \(10^9\), so we cannot create such an array. Instead, we:

• Record only the coordinates where values change in a dictionary
• At the end, sort only those coordinates and process them from left to right

There are at most 2 change points per tower, so at most \(2N\) in total. This is efficient enough to process.

Algorithm

1. Prepare an empty dictionary events.
2. For each tower, compute:
   • Left endpoint \(l = X_i - L_i\)
   • One past the right endpoint \(r+1 = X_i + R_i + 1\)

Then set: - events[l] += C_i - events[r+1] -= C_i

1. Sort the keys (change points) of events in ascending order.
2. Process from left to right:
   • Add events[x] to the current strength total cur
   • Update the maximum with ans = max(ans, cur)
3. Output ans.

At this point, cur right after computing cur += events[x] represents the value at all integer coordinates from \(x\) up to just before the next change point. Therefore, it is correct to update the maximum at that point.

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation notes

• Since the interval includes both endpoints \([l, r]\), it is important to subtract not at the right endpoint but at \(r+1\).

• Coordinates can be large and negative, so use a dictionary instead of an array.

• Multiple events can occur at the same coordinate, so accumulate them by adding in the dictionary.

• The maximum value should be updated after cur += events[x]. This is because the event is reflected at coordinate \(x\) itself.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    events = {}

    for _ in range(N):
        X, L, R, C = map(int, input().split())
        left = X - L
        right_plus_1 = X + R + 1

        events[left] = events.get(left, 0) + C
        events[right_plus_1] = events.get(right_plus_1, 0) - C

    cur = 0
    ans = 0
    for x in sorted(events):
        cur += events[x]
        if cur > ans:
            ans = cur

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.