ABC141C Attack Survival

Problem summary

You have an integer vector v whose length is N and whose initial element is K.
Now we have Q queries for updating v.
In query q_i ( $1 \le i \le Q$ ), you give an integer A_i and should decrement all other elements without A_i-th element of v (1-indexed). After executing Q queries, determine whether each elements are larger than 0 or not and print the result.

Constraints

・Time Limit: 2sec
・Memory Limit: 1024MB
・All values in input are integers
・ $2 \le N \le 10^5$
・ $1 \le K \le 10^9$
・ $1 \le Q \le 10^5$
・ $1 \le A_i \le N (1 \le i \le Q)$

Answer

blute-force

We simulate each queries in a row.
this takes O(N) per query so entire solution is O(NQ).

optimized

The answer is not depend on the order of queries so we can think only how many times i-th element of v is decremented ( $1 \le i \le N$ ). the result of i-th element of v is (k - q + cnt[i] > 0 ? "Yes" : "No")
This takes O(N + Q) and It's satisfy the time limit.