Overview

A problem where you use the difference between each item’s actual price and the old price list price to find the price discrepancy for each department’s purchase request.

Analysis

In this problem, for each item \(i\), we are given the “actual price \(P_i\)” and the “old price list price \(Q_i\)”. For each department’s desired item list, we need to compute the sum of differences \(P_i - Q_i\).

A straightforward approach would be, for each department, to iterate through the item numbers that department requests, computing and accumulating \(P_i - Q_i\) each time. However, this method is already sufficiently fast. Looking at the constraints, \(\sum K_j \leq 2 \times 10^5\), meaning the total length of all departments’ request lists is very small, so the total number of computations across all departments is at most around 200,000. Therefore, no special optimization is needed to meet the time limit.

However, reading input quickly is necessary. Python’s standard input() function is too slow, so it is preferable to use sys.stdin.read to read all input at once and process it.

Furthermore, by precomputing the difference \(D_i = P_i - Q_i\) for each item \(i\), the summation for each department becomes more efficient.

Algorithm

1. Read all input at once and store it in a list.
2. Precompute the difference \(D_i = P_i - Q_i\) for each item \(i\) (in the code, this may be computed directly at usage time, but it can also be stored in a separate array).
3. For each department, iterate through the requested item numbers and sum the corresponding \(P_c - Q_c\).
4. Output the results.

Complexity

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

Implementation Notes

• Since the input is very large, use sys.stdin.read for fast reading.

• For each department’s computation, computing \(P_c - Q_c\) on the fly is fine, but memoizing it may be even faster in some cases.

• It is efficient to output all results at once at the end (e.g., using print('\n'.join(result))).

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    P = [0] * (N + 1)
    Q = [0] * (N + 1)
    
    for i in range(1, N + 1):
        P[i] = int(data[idx])
        idx += 1
    for i in range(1, N + 1):
        Q[i] = int(data[idx])
        idx += 1
    
    result = []
    for _ in range(M):
        K = int(data[idx])
        idx += 1
        diff = 0
        for __ in range(K):
            c = int(data[idx])
            idx += 1
            diff += P[c] - Q[c]
        result.append(str(diff))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.