Overview

There are \(N\) radio towers on a road, each with a coverage range. The goal is to choose a single integer coordinate point and maximize the total signal strength from all towers covering that point. We solve this efficiently using event sorting (coordinate compression + sweep line).

Analysis

Problem with the Naive Approach

Each tower’s coverage range is \([X_i - L_i,\; X_i + R_i]\), and coordinates can span from \(0 - 10^9 = -10^9\) to \(10^9 + 10^9 = 2 \times 10^9\). Trying all integer coordinates would require up to \(2 \times 10^9\) computations, which is clearly too slow.

Key Insight

The total signal strength only changes at coordinates where a coverage range starts or ends. In other words, between consecutive event coordinates, the total strength remains constant. Therefore, it suffices to record the “start” and “end” of each coverage range as events and only scan the event coordinates. This is the sweep line method.

Event Definition

The coverage range of tower \(i\) is the integer coordinate interval \([X_i - L_i,\; X_i + R_i]\).

• Start event: \(+C_i\) at coordinate \(X_i - L_i\) (coverage begins)
• End event: \(-C_i\) at coordinate \(X_i + R_i + 1\) (coverage ends)

The reason the end event coordinate is \(X_i + R_i + 1\) is that the point \(X_i + R_i\) is still covered, so we need to cancel it at the next coordinate.

Event Order at the Same Coordinate

When start and end events exist at the same coordinate, we process end (\(-1\)) events first. The end event coordinate \(r+1\) means “no longer covered from \(r+1\) onward,” which is independent of any new coverage starting at the same coordinate. By using event types \(-1\) (end) and \(+1\) (start) as the sort key \((coordinate, type)\), since \(-1 < 1\), end events naturally come first.

Algorithm

1. For each tower \(i\), generate a start event \((X_i - L_i, +1, C_i)\) and an end event \((X_i + R_i + 1, -1, C_i)\).
2. Sort all events in ascending order by \((coordinate, type)\).
3. Initialize the current signal strength total current_sum to \(0\), then process events in order:
   • For a start event: current_sum += C_i
   • For an end event: current_sum -= C_i
   • After processing each event, update max_sum.
4. Output max_sum.

Concrete Example

Tower A: position \(3\), \(L=2\), \(R=1\), \(C=5\) → coverage \([1, 4]\) Tower B: position \(5\), \(L=1\), \(R=2\), \(C=3\) → coverage \([4, 7]\)

Events: \((1, +1, 5),\; (4, +1, 3),\; (5, -1, 5),\; (8, -1, 3)\)

• Coordinate \(1\): \(+5\) → total \(5\)
• Coordinate \(4\): \(+3\) → total \(8\) ← Maximum! (coordinate \(4\) is within both coverage ranges)
• Coordinate \(5\): \(-5\) → total \(3\)
• Coordinate \(8\): \(-3\) → total \(0\)

The answer is \(8\).

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the events)
• Space complexity: \(O(N)\) (storing the event list)

Implementation Notes

• Since coverage ranges are closed intervals on integer coordinates \([X_i - L_i,\; X_i + R_i]\), end events are placed at \(X_i + R_i + 1\) (a technique of converting to a half-open interval \([l, r+1)\)).

• To process end events before start events at the same coordinate, assign event types \(-1\) (end) and \(+1\) (start) and sort by coordinate and type together — this naturally produces the correct order.

• Even when \(N = 0\), the initial value \(0\) directly serves as the answer, so no special handling is needed.

  Source Code

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    
    events = []
    for i in range(N):
        X = int(input_data[idx]); idx += 1
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        C = int(input_data[idx]); idx += 1
        left = X - L
        right = X + R
        events.append((left, 1, C))      # start of coverage
        events.append((right + 1, -1, C)) # end of coverage (right+1 because inclusive)
    
    # Sort events by coordinate, then by type (starts before ends at same coordinate)
    events.sort(key=lambda e: (e[0], e[1]))
    
    # Sweep through events
    current_sum = 0
    max_sum = 0
    
    for coord, typ, c in events:
        if typ == 1:
            current_sum += c
        else:
            current_sum -= c
        if current_sum > max_sum:
            max_sum = current_sum
    
    # Wait, we need to be more careful. Events at the same coordinate should be processed together,
    # and we should check the sum after processing all events at each coordinate.
    # Also, we need to process adds before removes at the same coordinate to get the max.
    
    # Let me redo this properly with grouping by coordinate.
    
    # Actually, let me reconsider. At coordinate `left`, coverage starts (add C).
    # At coordinate `right+1`, coverage ends (subtract C).
    # Between consecutive event coordinates, the sum is constant.
    # We want the maximum sum at any point.
    # After processing all events at a coordinate, the current_sum is valid for [this_coord, next_coord).
    # But we also want to check the sum AT this coordinate after adds but before removes?
    # No - at coordinate `left`, we add. At coordinate `right+1`, we remove.
    # So at coordinate `right`, the coverage is still active. At `right+1` it's removed.
    # So processing: at each coordinate, process all +1 events first, then -1 events.
    # After processing +1 events and before -1 events, that's the sum "at this coordinate" if
    # this coordinate is a left endpoint. But actually we want: after all events at coordinate c,
    # the sum is valid for points in [c, next_event_coord - 1].
    # Hmm, but if at the same coordinate we have both adds and removes, the order matters.
    # At coordinate c: if something starts at c (add) and something ends at c (i.e., right+1 = c, remove),
    # the remove means coverage ended at c-1. The add means coverage starts at c.
    # So at point c, the add is active and the remove has happened. So we should process removes first? No.
    # Remove event at c means coverage ended at c-1, so at point c the coverage is gone -> remove first, then add.
    # Wait: event (right+1, -1, C) means at coordinate right+1, remove C. At point right+1, this tower no longer covers.
    # event (left, +1, C) means at coordinate left, add C. At point left, this tower covers.
    # So at the same coordinate, if we have both remove and add:
    # The remove should happen first (since the removal is for coverage that ended at coord-1),
    # then adds. After both, the sum is correct for this coordinate.
    # Let me re-sort: removes (-1) before adds (+1) at same coordinate.
    
    events.sort(key=lambda e: (e[0], e[1]))  # -1 < 1, so removes come first. Good.
    
    current_sum = 0
    max_sum = 0
    
    for coord, typ, c in events:
        if typ == 1:
            current_sum += c
        else:
            current_sum -= c
        if current_sum > max_sum:
            max_sum = current_sum
    
    print(max_sum)

main()

---

This editorial was generated by claude4.6opus-thinking.