Build a Contest [Codeforces Round #532 (Div. 2) B]

https://codeforces.com/contest/1100/problem/B

N種類の問題がある。
ここで、M個の問題が順番に作問される。
N種類の問題が全て1個以上作られた場合に、N種類の問題を1つずつ使ってコンテストを開く。
コンテストを開くと問題が1つずつ減る。
M個の問題が作問された、それぞれのタイミングでコンテストが開かれるか開かれないかを答えよ。
コンテストが開かれる→1, 開かれない→0

N,M≦10^5

解説

https://codeforces.com/contest/1100/submission/48333569

シミュレーションをする。
cnt[i] = 種類iの問題であって、作問されたがまだ使われてない問題数
pls := N種類の問題の中で作問されたがまだ使われてない問題数が正の問題種数
これらを使ってシミュレーションする。
a種類目の問題が来た場合は、cnt[a]++をするが、もともとcnt[a]=0ならplsも++しておく。
plsがNになったら、全て揃ったということなので、全ての問題種を--して、結果0になったらplsも--して、
1と出す。
そうでないなら0を出す。
　
ループだけを見ると、O(MN)になっていてTLEしそうだが、
O(N)はN種類揃った時点でしか実行されないので、M回ループがあっても、M/N位しか実行されない。
なので、一番深いところもO(M/N)*(N)=O(M)で間に合う。
（キュー系でよくある、キュー操作は出す回数＋入れる回数しか行えないので、ならし大丈夫という考え方もできる←この説明は蛇足かも）

int N, M, A[101010];
int cnt[101010];
int pls = 0;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        cin >> A[i];
        int a = A[i];
        if (cnt[a] == 0) pls++;
        cnt[a]++;

        if (pls == N) {
            printf("1");
            rep(j, 1, N+1) {
                cnt[j]--;
                if (cnt[j] == 0) pls--;
            }
        }
        else printf("0");
    }
    printf("\n");
}