競プロ典型90 010 - Score Sum Queries(★2)
問題
https://atcoder.jp/contests/typical90/tasks/typical90_j
考察
学籍番号番までの期末試験点数の合計を各組に対して求める問題。
番目までの区間が連番なので累積和で求められそう。
と思ったが組が分かれており累積和が使いづらいので、ちょっと他のパターンを考えてみる。
いや、1組、2組それぞれの累積和で考えてみる。
各組の学籍番号が抜けている人がいる場合は点数を0として換算すれば累積和が使えそう。
例えば、このような組、点数の場合を考える。
1 72 2 78 2 94 1 23 2 89 1 40 1 75
1組 ] 2組 ]
それぞれの組に対する累積和を用いれば答えが簡単に求められそう。
提出コード
N = int(input()) A = [0] * N B = [0] * N for i in range(N): C, P = map(int,input().split()) if C == 1: A[i] = P elif C == 2: B[i] = P A_cumsum = [] B_cumsum = [] for i in range(N): if i == 0: A_cumsum.append(A[i]) B_cumsum.append(B[i]) else: A_cumsum.append(A_cumsum[i-1] + A[i]) B_cumsum.append(B_cumsum[i-1] + B[i]) Q = int(input()) for i in range(Q): L, R = map(int,input().split()) L -= 1 R -= 1 if L == 0: ans_1 = A_cumsum[R] ans_2 = B_cumsum[R] else: ans_1 = A_cumsum[R] - A_cumsum[L-1] ans_2 = B_cumsum[R] - B_cumsum[L-1] print(ans_1, ans_2)