Overview

For each supply item, precompute “actual price \(P_i\) − old table price \(Q_i\)”, then for each department’s request list, sum up the corresponding differences to find the total discrepancy.

Analysis

The value we want to find for each department \(j\) is: $\(\sum_{k=1}^{K_j} (P_{C_{j,k}} - Q_{C_{j,k}})\)\( The key observation here is that we don't need to subtract \)P\( and \)Q$ repeatedly for each department.

• If we first create the difference \(D_i = P_i - Q_i\) for each supply item \(i\), then the answer for department \(j\) is simply: $\(\sum_{k=1}^{K_j} D_{C_{j,k}}\)$
• This way, we just need to look up the supply item numbers in each request and add up values from the difference array.

The naive approach (computing \((P_i - Q_i)\) on the fly for each department and summing) has the same computational complexity, but in terms of implementation, “creating a difference array and summing” is simpler and faster than “writing the subtraction many times.”

Additionally, since the constraint \(\sum K_j \le 2\times 10^5\) is given, the optimal approach is to scan each department’s list for a total number of iterations equal to \(\sum K_j\). Conversely, an implementation that, for example, “scans \(1..N\) for each department to check if each item is included” would be \(O(MN)\) and would certainly result in TLE.

Concrete example: - If supply item 1 has difference \(D_1=100\) and supply item 3 has \(D_3=-50\), then if a department purchases \(\{1,3\}\), the answer is \(100+(-50)=50\).

Algorithm

1. Read \(P, Q\) from input and create the difference array \(D\) for each supply item: \(D_i = P_i - Q_i\).
2. For each department:
   • Read \(K_j\) and the supply item number sequence \(C_{j,1..K_j}\)
   • Starting from \(s=0\), for each \(c\), compute \(s \mathrel{+}= D_{c}\) (note the index adjustment to \(c-1\) for \(0\)-indexed arrays)
   • Output \(s\)

Complexity

• Time complexity: \(O(N + \sum_{j=1}^{M} K_j)\) (\(O(N)\) for creating the difference array, plus a total of \(\sum K_j\) operations for processing each request)
• Space complexity: \(O(N)\) (for storing the difference array \(D\))

Implementation Notes

• Supply item numbers \(C_{j,k}\) are \(1\)-indexed, so when using them with Python arrays, convert to \(c-1\).

• Since \(\sum K_j\) is at most \(2\times 10^5\) and \(N,M\) are at most \(10^5\), reading all input at once with sys.stdin.buffer.read() and extracting values sequentially with an iterator is fast.

• The difference can be negative, so handle it as a signed integer as-is (no issue in Python).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    P = [next(it) for _ in range(N)]
    Q = [next(it) for _ in range(N)]
    D = [p - q for p, q in zip(P, Q)]

    out = []
    for _ in range(M):
        k = next(it)
        s = 0
        for _ in range(k):
            c = next(it) - 1
            s += D[c]
        out.append(str(s))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.