Overview

This is a simulation problem where, for each purchase record, you determine the unit price based on whether the customer is a member or not, multiply by the quantity purchased, and sum up the totals.
The answer can be obtained by efficiently looking up product prices and processing the \(M\) records in order.

Analysis

There are two important points:

• The regular price of product \(i\) is given in array \(A\), so \(A_{P_j}\) can be immediately retrieved from the product number \(P_j\).
• Only when the customer is a member does the unit price become \(\max(A_{P_j} - K, 0)\) (it does not go below 0).

Therefore, for each purchase record \((S_j, P_j, D_j)\):

• Non-member (\(S_j=0\)): unit price \(= A_{P_j}\)
• Member (\(S_j=1\)): unit price \(= \max(A_{P_j}-K,0)\)

Compute these and sum up the amounts \(= \text{unit price} \times D_j\).

A naive approach such as “searching through all products for each record” would cost \(O(N)\) per record, resulting in \(O(NM)\) overall.
Given the constraints \(N \le 2\times 10^5,\ M \le 10^5\), this approach would not be fast enough.

On the other hand, since product numbers are consecutive integers from 1 to \(N\), they can be looked up in \(O(1)\) via array access.
This allows the entire problem to be processed in \(O(M)\) (or \(O(N+M)\) including input reading).

Algorithm

1. Read \(N, M, K\).
2. Read the regular price array \(A\) (in Python, which uses 0-indexing, the price of product \(p\) is A[p-1]).
3. Initialize total = 0.
4. For each purchase record, do the following:
   • price = A[p-1]
   • If s == 1 (member), then price = max(price - K, 0)
   • total += price * d
5. Output total.

Complexity

• Time complexity: \(O(N + M)\)
  (Reading the price array: \(O(N)\), processing purchase records: \(O(M)\))
• Space complexity: \(O(N)\)
  (Storing the price array \(A\))

Implementation Notes

• Product numbers are 1-indexed while arrays are 0-indexed, so be careful to use A[p-1].

• The member discount uses max(price - K, 0) to prevent negative values.

• The total amount can become large, but with Python’s int, there is no need to worry about overflow.

• Since the input can be large, using sys.stdin.readline ensures stable and fast performance.

  Source Code

import sys

def main():
    input = sys.stdin.readline

    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))

    total = 0
    for _ in range(M):
        s, p, d = map(int, input().split())
        price = A[p - 1]
        if s == 1:
            price = max(price - K, 0)
        total += price * d

    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.