Official

B - Yellow and Red Card Editorial by en_translator


This problem has several approaches. Since the constraints are small enough, any solution that obeys the rules in the problem statement will be accepted.
For example, we can come up with the following simple algorithm:

  • Prepare a list \(v\) that stores the past events, which is initially empty.
  • For each \(i = 1, 2, \dots, N\):
    • receive the \(i\)-th event \((c_i, x_i)\). Depending on \(c_i\),
      • do nothing if \(c_i=1,2\);
      • if \(c_i = 3\), inspect all the events up to the \((i-1)\) one by scanning \(v\) to count the number of yellow and red cards that person \(x_i\) received. If the number of cards satisfies the condition for the removal, print Yes; otherwise, print No.
    • Then, add \((c_i,x_i)\) to \(v\).

This algorithm scans \((i-1)\) events in the \(i\)-th query, so the scan may cost be up to \(\sum_{i=1}^Q (i-1) = \frac{Q^2-Q}{2}\) steps. Thus, the complexity is \(\mathrm{O}(Q^2)\).

The algorithm above is fast enough to get AC (accepted), but we may improve the complexity to \(\mathrm{O}(N + Q)\) with a little tweak.
In order to reduce the complexity, we use arrays to record the number of yellow card that each person received, and whether each person was removed, and update them for every event. This way, we do no longer need to scan all the event for each question, leading to a speed up.
Specifically, implement the following procedure.

  • Prepare a length-\(N\) array \(y\) that records “how many yellow cards did person \(x\) received?” and another length-\(N\) array \(r\) that records “was person \(r\) removed?”. \(y\) is initialized with \(0\), and \(r\) with false.
  • For each \(i = 1, 2, \dots, N\):
    • receive the \(i\)-th event \((c_i, x_i)\). Depending on \(c_i\),
      • if \(c_i = 1\), increment \(y[x]\) by \(1\). If \(y[x]\) reaches by \(2\), person \(x\) is removed so let \(r[x]\) be true.
      • If \(c_i = 2\), person \(x\) is removed, so let \(r[x]\) be true.
      • If \(c_i = 3\), print Yes if \(r[x]\) is true and No otherwise.

The complexity is \(\mathrm{O}(N + Q)\). This algorithm enables us to write a code that works even with \(N, Q \leq 10^5\).

  • Sample code (C++)
#include <iostream>
#include <vector>
using namespace std;
int main() {
  int N, Q;
  cin >> N >> Q;
  vector<int> r(N + 1), y(N + 1);
  while (Q--) {
    int cmd, x;
    cin >> cmd >> x;
    if (cmd == 1) {
      y[x]++;
      if (y[x] == 2) r[x] = 1;
    } else if (cmd == 2) {
      r[x] = 1;
    } else {
      cout << (r[x] ? "Yes" : "No") << endl;
    }
  }
}

Bonus (worth problem C): how can we support \(N = 10^{18}\) and \(Q = 10^5\) fast enough?

posted:
last update: