Overview

For \(N\) types of supplies, you are given the actual price \(P_i\) and the old price list price \(Q_i\). The problem asks you to find the difference between the “actual total cost” and the “estimated total cost” when purchasing supplies specified in each of \(M\) departments’ lists.

Analysis

The value each department needs can be expressed as follows, where \(C_1, C_2, \ldots, C_K\) are the supply item numbers to purchase: $\(\sum_{k=1}^{K} (P_{C_k} - Q_{C_k})\)$

Looking closely at this formula, we can see that by precomputing the “difference between actual price and estimated price” for each supply item \(i\), the calculation can be simplified.

1. Precomputing the differences: For each supply item \(i\), compute \(D_i = P_i - Q_i\) in advance.
2. Answering queries: The total difference for department \(j\) is simply \(\sum_{k=1}^{K_j} D_{C_{j,k}}\).

For example, if supply 1 has prices \(P_1=100, Q_1=80\), then \(D_1=20\). If supply 2 has \(P_2=50, Q_2=60\), then \(D_2=-10\). When purchasing both, the total difference is \(20 + (-10) = 10\), which gives the same result as subtracting individually and then summing.

Constraints and Efficiency

• \(N, M\) are at most \(10^5\), and the total number of supplies purchased across all departments \(\sum K_j\) is \(2 \times 10^5\).
• Even computing \(P_i - Q_i\) each time per department would be fast enough, but by storing \(D_i\) in an array beforehand, each query only needs to look up and sum array values (\(O(K_j)\)), which runs very efficiently.
• Since the amount of input/output data is large, in Python it is recommended to use fast I/O methods such as sys.stdin.read instead of the standard input().

Algorithm

1. Prepare an array \(D\) of length \(N\) and store \(D_i = P_i - Q_i\).
2. Repeat the following process for each of the \(M\) departments:
   • Read the \(K_j\) supply item numbers \(C_{j,k}\) from input.
   • Sum up the corresponding differences \(D_{C_{j,k}}\) for each item number.
   • Output the total.

Complexity

• Time complexity: \(O(N + \sum K_j)\)
  • Precomputing the differences takes \(O(N)\).
  • Processing all department queries requires a total of \(\sum K_j\) additions, taking \(O(\sum K_j)\).
  • Overall, it can be processed in linear time with respect to the input size.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the arrays storing prices and differences.

Implementation Notes

• Handling 1-indexed values: The supply item numbers in the problem are from \(1\) to \(N\), but arrays in programs typically start from \(0\), so you need to adjust the index like D[i - 1].

• Fast I/O: In Python, you can efficiently process large amounts of data by reading all input at once with sys.stdin.read().split() and using an iterator (iter()). It is also effective to accumulate results in a list and output them all at once with '\n'.join().

  Source Code

import sys
from itertools import islice

def main():
    # 入力を一括で読み込み、空白で分割してリスト化することで高速化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して各要素を順番に取得します
    it = iter(input_data)
    
    # N: 備品の種類数, M: 部署の数
    N = int(next(it))
    M = int(next(it))
    
    # P: 実際の価格, Q: 古い価格表の価格
    # isliceとmapを使用して効率的に整数リストに変換します
    P = list(map(int, islice(it, N)))
    Q = list(map(int, islice(it, N)))
    
    # 各備品について、実際の価格と見積もり価格の差額 (P_i - Q_i) をあらかじめ計算します
    # 備品番号は1から始まるため、リストDのインデックスiは備品番号i+1に対応します
    D = [p - q for p, q in zip(P, Q)]
    
    results = []
    # 各部署の購入申請を処理します
    for _ in range(M):
        # K: 購入する備品の個数
        K = int(next(it))
        
        # 次のK個の要素（備品番号）を整数に変換し、その差額の合計を計算します
        # map(int, islice(it, K)) でK個の備品番号を効率的に取得します
        # 備品番号は1-indexedなので、D[i - 1]でアクセスします
        diff_sum = sum(D[i - 1] for i in map(int, islice(it, K)))
        
        # 結果を文字列としてリストに追加します
        results.append(str(diff_sum))
        
    # すべての結果を改行で連結して一括出力します
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    main()

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