Solução Informática - Nível Intermediário - Semana 21

Solução por Pedro Racchetti

Conteúdos utilizados:

Para resolver esse problema, primeiro temos que notar que, inicialmente, existe exatamente um quarteirão já que no inicio, nenhum prédio está abaixo do nível do mar. Além disso, podemos notar que no máximo $n+d$ dias nos interessam, não $10^9$ . Esses dias são todos os dias que o prefeito deseja saber o número de quarteirões, e todos os dias em que um prédio se torna alagado.

Tendo essas observações, podemos ordenar os prédios, de menor para maior. Então, passamos por todos os dias de indagação do prefeito, e processamos todos os prédios que estão a baixo do nível do mar dele. Inicializaremos a resposta como $1$ , e diremos que todos os prédios estão acima do mar. Quando processarmos um prédio, verificamos se os prédios aos lados dele estão abaixo do nível do mar. Se os dois estiverem, então esse prédio era um quarteirão, e vai deixar de ser, portanto diminuímos em $1$ a resposta. Se nenhum dos dois estão abaixo do nível do mar, um novo quarteirão foi formado, e portanto aumentamos em um a resposta. Podemos manter os estados dos prédios (abaixo ou acima do nível do mar) em um vetor de marcação.

Esse algoritmo porém teria complexidade de $O(nd)$ , que é muito devagar. Com a ideia de Two-Pointers, podemos acelerar ele para $O(n+d)$ . Mantendo um iterador nos prédios ordenados, enquanto processamos o dia, na ordem de entrada, podemos passar pelos dias indagados, e quando processar um dia, avançaremos com o iterador dos prédios, processando o prédio em questão a cada passo, até atingirmos um prédio que tenha altura maior que o dia processado, que será processado apenas no próximo dia indagado.

Segue o código, comentado, para melhor compreensão do problema.

	#include<bits/stdc++.h>
	using namespace std;
	//Funções dadas pelo problema, para acelerar a leiura e impressão de dados.
	void getint(int &x){
	register int c = getchar_unlocked();
	x = 0;
	for(;(c<48 \|\| c>57);c = getchar_unlocked());
	for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c - 48;}
	}

	inline void print(int n){
	if (n == 0)
	{
	putchar_unlocked('0');
	putchar_unlocked('\n');
	}
	else if (n == -1)
	{
	putchar_unlocked('-');
	putchar_unlocked('1');
	putchar_unlocked('\n');
	}
	else
	{
	char buf[11];
	buf[10] = ' ';
	int i = 9;
	while (n)
	{
	buf[i--] = n % 10 + '0';
	n /= 10;
	}
	while (buf[i] != ' ')
	putchar_unlocked(buf[++i]);
	}
	}

	const int MAXN = 1e6 + 10;
	pair<int,int> predios[MAXN]; //Guardaremos os predios como um vetor de pares, que guardam a altura e a posicao dele
	int marc[MAXN],predio,resp,n,q;

	int main(){
	int TC;
	scanf("%d",&TC);
	while(TC--){
	getint(n);
	getint(q);
	for(int i=1;i<=n;i++){
	int a;
	getint(a);
	predios[i] = make_pair(a,i);
	marc[i] = 1; //inicialmente, todos os predios estão acima do nivel do mar.

	}
	marc[0] = 0; //não existe um prédio na posição 0
	marc[n+1] = 0; //não existe um prédio na posição n + 1
	sort(predios+1,predios+n+1); //ordenamos os prédios pela altura.
	resp = 1; //inicialmente, existe apenas 1 quarteirão.
	predio = 1;
	for(int i = 0; i < q; i++){
	int d;
	getint(d);
	while(predio <= n && predios[predio].first <= d){
	//enquanto o prédio está abaixo do nível do mar, processaremos os prédios
	int pos = predios[predio].second;
	if(marc[pos-1] == 0 && marc[pos+1] == 0){
	//quando os dois vizinhos do prédio atual já estão submergidos, diminuimos o numero de quarteiroes
	resp--;
	}
	else if(marc[pos-1] == 1 && marc[pos + 1] == 1){
	//Quando os dois vizinhos do prédio atual estão acima do nível do mar, um novo quarteirão é criado
	resp++;
	}
	//o prédio processado não está mais acima do nível do mar.
	marc[pos] = 0;
	predio++;
	}
	print(resp);
	}
	printf("\n");
	}
	return 0;
	}

view raw

arranhaceu.cpp

hosted with ❤ by GitHub