Simulado NOIC - Segunda Fase OBI 2021

binario.cpp

// Simulado NOIC - Segunda Fase OBI 2021
// Binário
// Complexidade: O(N + M log N)
// Escrito por Lúcio Figueiredo

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;

int a[maxn];

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	// set[0] e set[1]
	set<int> st[2];

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);

		if (a[i] == 0) st[0].insert(i);
		else st[1].insert(i);
	}

	for (int i = 1; i <= m; i++)
	{
		int pos; // posição a ser atualizada
		scanf("%d", &pos);

		// atualizamos os sets e o valor de a[pos]
		st[a[pos]].erase(pos);

		a[pos] = !a[pos];

		st[a[pos]].insert(pos);

		// checamos inicialmente se algum dos sets está vazio; se sim, o vetor está ordenado
		// após isso, checamos se o maior elemento de st[0] (seu *rbegin) é menor que o menor elemento de st[1] (seu *begin)
 		if (st[0].size() == 0 || st[1].size() == 0 || *st[0].rbegin() < *st[1].begin()) printf("1\n");
		else printf("0\n");
	}
}