Overview

Given multiple radio towers placed on a line, each with a coverage range (interval) and signal strength (weight), the problem asks to find the maximum total signal strength that can be received at any single point.

Analysis

This problem can be rephrased as “find the maximum total weight at the point where weighted intervals overlap the most.”

Naive Approach

If we try to compute the signal strength at every integer coordinate, the coordinate range extends from \(0\) to over \(10^9\), so the computation would not finish in time and result in a Time Limit Exceeded (TLE) verdict.

Key Insight

The total signal strength only changes at the points where some tower’s coverage range begins or ends. The coverage range of tower \(i\) is \([X_i - L_i, X_i + R_i]\). Therefore, the candidate coordinates where the total changes are limited to: - Range start: \(X_i - L_i\) - Just after range end: \(X_i + R_i + 1\)

At all other points, moving to an adjacent coordinate does not change the total strength. Thus, by efficiently processing only these “event coordinates,” we can find the maximum value.

Algorithm

We use a technique called the “imos method” or “sweep line method.”

1. Event enumeration: For each tower \(i\), create the following 2 events:
   • At coordinate \(X_i - L_i\), add strength \(C_i\).
   • At coordinate \(X_i + R_i + 1\), subtract strength \(C_i\).
2. Sort: Sort all created events in ascending order of coordinate.
3. Sweep: Process the sorted events in order, updating the current total signal strength (current_strength).
   • If multiple events occur at the same coordinate, aggregate all of them before checking for the maximum.
   • Record the maximum value of current_strength at each step.

Complexity

• Time complexity: \(O(N \log N)\) The number of events is \(2N\). Sorting them takes \(O(N \log N)\). The subsequent sweep completes in \(O(N)\), so the overall complexity is dominated by the sort.
• Space complexity: \(O(N)\) Memory is needed to store the list of \(2N\) events.

Implementation Notes

• Range endpoint: Since the problem states that tower \(i\) covers up to \(X_i + R_i\) inclusive, the strength decrease occurs at the next coordinate, \(X_i + R_i + 1\).

• Events at the same coordinate: When “start” and “end” events occur simultaneously at the same coordinate, they should be processed together before updating the maximum. In the Python code, a while loop is used to batch-process events at the same coordinate.

• Fast input: Since \(N\) can be as large as \(10^5\), reading all input at once using sys.stdin.read().split() is faster than calling input() repeatedly, reducing execution time.

  Source Code

import sys

# 競技プログラミングのエキスパートとして、以下の問題を解くコードを実装します。
# 道路上の任意の整数座標において、受信できる信号の強度の合計を最大化する問題です。
# 各電波塔 i のカバー範囲は [X_i - L_i, X_i + R_i] で、その強度は C_i です。
# この問題は、重み付き区間の最大重み地点を見つける問題として、
# スイープ法（平面走査法）を用いて O(N log N) で解くことができます。

def solve():
    # 標準入力からすべてのデータを読み込みます。
    # 大量のデータを扱うため、sys.stdin.read().split() を使用して高速にパースします。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # 電波塔の数 N
    N = int(input_data[0])
    
    # イベントを格納するリスト。各イベントは (座標, 強度の変化) のタプルです。
    events = []
    
    # 各電波塔のデータをパースし、イベントを作成します。
    # 電波塔 i は [X_i - L_i, X_i + R_i] の範囲をカバーします。
    for i in range(N):
        base_idx = 1 + i * 4
        x = int(input_data[base_idx])
        l = int(input_data[base_idx + 1])
        r = int(input_data[base_idx + 2])
        c = int(input_data[base_idx + 3])
        
        # 座標 (x - l) で信号強度 c が加算されます。
        events.append((x - l, c))
        # 座標 (x + r) まで信号が届くため、(x + r + 1) で信号強度 c が減算されます。
        events.append((x + r + 1, -c))
        
    # イベントを座標の昇順にソートします。
    # 同じ座標に複数のイベントがある場合でも、まとめて処理することで正しく計算できます。
    events.sort()
    
    max_strength = 0
    current_strength = 0
    
    i = 0
    num_events = len(events)
    
    # スイープラインを動かして最大値を求めます。
    while i < num_events:
        curr_x = events[i][0]
        
        # 同じ座標で発生するすべてのイベント（信号の開始・終了）を合算します。
        # これにより、その座標における正確な合計信号強度が得られます。
        while i < num_events and events[i][0] == curr_x:
            current_strength += events[i][1]
            i += 1
        
        # 現在の座標における合計強度がこれまでの最大値を超えていれば更新します。
        if current_strength > max_strength:
            max_strength = current_strength
            
    # 最終的な最大信号強度を出力します。
    sys.stdout.write(str(max_strength) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.