タイムアウトによりプログラムが終了しました

Question

問題：

サイズNのリストが与えられ、ゼロで初期化されています。リストに対してM操作を実行し、リスト内のすべての要素の最終値の最大値を出力する必要があります。すべての操作に対して、a、b、およびkの3つの整数が与えられ、インデックスaからb（両方を含む）までのすべての要素に値を追加する必要があります。

入力フォーマット

最初の行は、単一のスペースで区切られた2つの整数NとMが含まれています。 次の行には、3つの整数a、b、およびkが1つのスペースで区切られています。ここでは、リスト内の 番号1からNまで番号が付けられている

は、私が書いたコードです：

n,m=map(int,input().split()) 
arr=[] 
for i in range(n+1): 
    arr.append(0) 
for j in range(m): 
    a,b,k=map(int,input().split()) 
    for i in range(a,b+1): 
     arr[i]+=k; 

print(max(arr))  

私は私の解決策を提出しようとすると私は、「DUE TIMOUTに終端」を取得message.Couldあなたはこれらの種類のエラーを避けるための戦略を提案し、問題の解決策も提案してください。

ありがとうございます！

Answer 1

リスト範囲をループしないでください。代わりにmapを使用して、示された値をインクリメントしてください。何かのように

for j in range(m): 
    a,b,k=map(int,input().split()) 
    arr[a:b+1] = map(lambda <increment-by-k>, arr[a:b+1]) 

これはあなたの居住者の最適化が膨大な時間を節約し、時間を節約する必要があります。

Answer 2

おそらく、O（M * N）よりも複雑なアルゴリズムが必要です。

あなたがリストに間隔区切り文字を入れることができます。

n,m=map(int,input().split()) 
intervals = [] 
arr = [0 for i in range(n)] 

for j in range(m): 
    a,b,k=map(int,input().split()) 
    intervals += [(str(a), "begin", k)] 
    intervals += [(str(b), "end", k)] 
intervals = sorted(intervals, key=lambda x: x[0]+x[1]) 

k, i = 0, 0 
for op in intervals: 
    ind = int(op[0]) 
    if op[1] == "begin": 
     while ind > i: 
      arr[i] += k 
      i += 1 
     k += op[2] 
    else: 
     while i <= ind: 
      arr[i] += k 
      i+= 1 
     k -= op[2] 

print(arr) 

ソートアルゴリズムはO（MlogM）であれば、これはあなたがまた、入力値を投稿することができますO（MlogM + N）