概要

各区間にかかる時間を前処理することで、各グループの見学終了時刻を高速に求めることができる。

考察

各グループは、指定された区間 \([L_j, R_j]\) 内のエリアをすべて見学する必要があり、その合計時間は
$\( T_{L_j} + T_{L_j+1} + \cdots + T_{R_j} \)\( となる。これを毎回愚直に計算すると、最悪ケースで \)O(N)\( かかり、全体で \)O(MN)$ となり、制約が大きいためTLEしてしまう。

そこで、累積和を用いることで区間和を \(O(1)\) で求めることを考える。
累積和配列 \(prefix\_sum\) を以下のように定義する：
$\( prefix\_sum[i] = T_1 + T_2 + \cdots + T_i \)\( このとき、区間 \)[L, R]\( の合計は次のように求められる： \)\( \text{sum}(L, R) = prefix\_sum[R] - prefix\_sum[L - 1] \)\( これにより、各クエリに対して区間の合計が \)O(1)\( で求められ、全体で \)O(N + M)$ となる。

アルゴリズム

1. 各エリアの見学時間 \(T_i\) を読み込み、累積和配列 \(prefix\_sum\) を構築する。
2. 各グループについて、到着時刻 \(S_j\) に加えて区間 \([L_j, R_j]\) の合計時間を累積和から求める。
3. 合計時間を到着時刻に加えたものが、そのグループの見学終了時刻である。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 累積和を計算する際に、先頭に 0 を追加しておくと、\(prefix\_sum[L - 1]\) が存在しない場合の例外処理が不要になる。

• 入力を一度に読み込んで分割する方法（sys.stdin.read）を使うことで、高速な入力処理が可能になる。

  ソースコード

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    T = list(map(int, data[2:2+N]))
    
    # 累積和を計算 (1-indexed)
    prefix_sum = [0] + list(accumulate(T))
    
    idx = 2 + N
    results = []
    
    for _ in range(M):
        S = int(data[idx])
        L = int(data[idx+1])
        R = int(data[idx+2])
        idx += 3
        
        # 区間 [L, R] の合計時間 = prefix_sum[R] - prefix_sum[L-1]
        total_time = prefix_sum[R] - prefix_sum[L-1]
        finish_time = S + total_time
        results.append(finish_time)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。