arranhaceu.cpp

#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;
}