Overview

For each piece of equipment, precompute the difference “actual price - old price list price”, then for each department’s purchase request, sum up the differences for the corresponding equipment.

Analysis

Understanding the Essence of the Problem

The value we want to compute for each department is given by the following formula: $\(\sum_{k=1}^{K_j} (P_{C_{j,k}} - Q_{C_{j,k}})\)$

This means “for each piece of equipment the department wishes to purchase, sum up the differences between the actual price and the old price list price.”

Key Observation

The part \(P_{C_{j,k}} - Q_{C_{j,k}}\) is a value determined solely by the equipment number \(C_{j,k}\). In other words, once we compute the difference \(D_i = P_i - Q_i\) for equipment \(i\), we can reuse it as many times as needed.

Issues with a Naive Approach

Even if we separately look up \(P_i\) and \(Q_i\) each time and subtract, the computational complexity doesn’t change. However, precomputing the difference \(D_i\) offers the following advantages: - The code becomes simpler - The number of array accesses is reduced (from 2 to 1)

Checking the Input Size

• \(N, M \leq 10^5\)
• \(\sum_{j=1}^{M} K_j \leq 2 \times 10^5\) (total number of purchase requests across all departments)

Even if we process all purchase requests straightforwardly, the total number of operations is about \(2 \times 10^5\), which is sufficiently fast.

Algorithm

1. Read input: Read the actual prices \(P_i\) and the old price list prices \(Q_i\) for each piece of equipment.

2. Precompute differences: For each piece of equipment \(i\), compute the difference \(D_i = P_i - Q_i\) and store it in an array.

3. Process each department’s request:

   • For department \(j\), read the equipment numbers \(C_{j,1}, C_{j,2}, \ldots, C_{j,K_j}\) it wishes to purchase.
   • Sum up the corresponding differences \(D_{C_{j,1}}, D_{C_{j,2}}, \ldots, D_{C_{j,K_j}}\).
   • Append the result to the output list.

4. Output the results: Output all department results together.

Concrete Example

For the input: \(N=3\), \(P = [100, 200, 300]\), \(Q = [90, 220, 300]\)

Difference array: \(D = [10, -20, 0]\)

If a department wishes to purchase equipment \(1, 2\), the answer is \(D_1 + D_2 = 10 + (-20) = -10\).

Complexity

• Time complexity: \(O(N + \sum_{j=1}^{M} K_j)\)

  • \(O(N)\) for precomputing the difference array
  • \(O(\sum_{j=1}^{M} K_j)\) for processing all departments’ purchase requests
  • Given the constraints, the overall complexity is about \(O(N + 2 \times 10^5) = O(N + M)\)

• Space complexity: \(O(N + M)\)

  • \(O(N)\) for the price arrays \(P, Q\) and the difference array \(D\)
  • \(O(M)\) for the array storing the results

Implementation Notes

1. 1-indexed arrays: Since equipment numbers range from \(1\) to \(N\), it is clearer to set the array size to \(N+1\) and use 1-indexed access.

2. Fast input: By reading all input at once with sys.stdin.read() and splitting with split(), large inputs can be processed efficiently.

3. Batch output: By accumulating results in a list and outputting them all at once with '\n'.join() at the end, output speed can be improved.

4. Watch out for negative values: When \(P_i < Q_i\), the difference becomes negative. The problem statement explicitly mentions that “the result may be negative.”

   Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    
    N = int(input_data[idx])
    M = int(input_data[idx + 1])
    idx += 2
    
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    
    for i in range(1, N + 1):
        P[i] = int(input_data[idx])
        idx += 1
    
    for i in range(1, N + 1):
        Q[i] = int(input_data[idx])
        idx += 1
    
    # 差額を事前計算: D[i] = P[i] - Q[i]
    D = [0] * (N + 1)
    for i in range(1, N + 1):
        D[i] = P[i] - Q[i]
    
    results = []
    for _ in range(M):
        K = int(input_data[idx])
        idx += 1
        
        diff_sum = 0
        for _ in range(K):
            c = int(input_data[idx])
            idx += 1
            diff_sum += D[c]
        
        results.append(diff_sum)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.