Overview

For each payment, we add the difference \(D_j\) by treating “the person who paid upfront as plus” and “each person who used the service as minus by their equal share.” The goal is to compute the final values \(D_1,\dots,D_N\).

Analysis

The desired \(D_j\) is the difference between:

• The total amount actually paid upfront (the sum of what one paid out of pocket)
• The total amount one should have borne (the sum of equal shares from payments one participated in)

The key insight here is that we can look at each payment independently and directly add/subtract to \(D\).

Considering payment \(i\):

• The person \(P_i\) who paid upfront spent \(C_i\) yen on the spot, so add \(+C_i\) to \(D_{P_i}\)
• There are \(K_i\) users sharing equally, so each user’s share is \(\frac{C_i}{K_i}\)
  • Therefore, for each user \(b\), subtract \(-\frac{C_i}{K_i}\) from \(D_b\)

Summing this over all payments directly gives us \(D_j\) as defined.

Where a naive approach can go wrong

For instance, if you try to construct specific transactions like “who pays how much to whom,” the bookkeeping becomes complex when there are many people. However, this problem only requires knowing the final difference \(D_j\); the specific transaction paths are unnecessary.

Also, while we do need to distribute the equal share to all users, the constraint guarantees \(\sum K_i \le 10^5\), so the total number of iterations over users is at most \(10^5\), which is fast enough.

(Example) - With 3 people, if person 1 pays upfront \(C=600\) yen for users {1,2,3} (\(K=3\)): - \(D_1 += 600\) - Each user gets \(-200\) → \(D_1 -=200, D_2 -=200, D_3 -=200\) - Result: \(D_1=+400, D_2=-200, D_3=-200\) (person 1 receives 400 yen; persons 2 and 3 each pay 200 yen)

Algorithm

1. Initialize array \(D[1..N]\) to \(0\).
2. For each payment \((P_i, C_i, K_i, B_{i,1..K_i})\):
   1. \(D[P_i] \mathrel{+}= C_i\)
   2. \(\text{share} = \frac{C_i}{K_i}\) (guaranteed to be an integer)
   3. For each user \(b \in \{B_{i,1},\dots,B_{i,K_i}\}\), do \(D[b] \mathrel{-}= \text{share}\)
3. Finally, output \(D[1], D[2], \dots, D[N]\).

This method simply accumulates “paid upfront = plus” and “share of burden = minus” exactly as defined, so it correctly computes \(D_j\).

Complexity

• Time complexity: \(O\!\left(N + M + \sum_{i=1}^{M} K_i\right)\) (effectively \(O(N + M + 10^5)\))
• Space complexity: \(O(N)\)

Implementation Notes

• \(C_i\) can be up to \(10^9\), and with multiple payments, \(D_j\) can become large. Python’s int handles this without issues (for other languages, 64-bit integers are recommended).

• Since the input size can be large, reading all input at once with sys.stdin.buffer.read() and processing it as a sequence of integers is faster.

• Since person numbers are \(1..N\), using an array of size N+1 with 1-based indexing makes implementation straightforward.

  Source Code

import sys

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

    D = [0] * (N + 1)

    for _ in range(M):
        P = next(it)
        C = next(it)
        K = next(it)
        D[P] += C
        share = C // K
        for _ in range(K):
            b = next(it)
            D[b] -= share

    out = "\n".join(str(D[i]) for i in range(1, N + 1))
    sys.stdout.write(out)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.