Papel OBI f2p2 2017 comentário NOIC

papel.cpp

// Papel - F2P2 - OBI 2017
// Bia Cunha
// Complexidade: O(nlog)

#include <bits/stdc++.h>
#define MAXN 100010

using namespace std;

int n;
int h;
vector<int> retangulos;
map<int, int> m;
map<int, int> ::iterator it;

int main(){
	//lê a quantidade de retângulos
	scanf("%d", &n);
	
	//adiciona 0 no início
	retangulos.push_back(0);

	for(int i=0; i<n; i++){
		//lê novo retângulo
		scanf("%d", &h);
		
		//se ele é diferente
		if(h != retangulos.back()) retangulos.push_back(h);
	}
	
	//adiciona 0 no final
	retangulos.push_back(0);
 
	for(int i=1; i<retangulos.size()-1; i++){
		//se o retângulo i é um pico, ou seja, maior que o anterior e que o seguinte,
		if(retangulos[i] > retangulos[i-1] && retangulos[i] > retangulos[i+1])
			//salva em pv como pico (-1)
			pv.push_back( make_pair(retangulos[i], -1) );
		
		//se o retângulo i é um vale, ou seja, maior que o anterior e que o seguinte,
		if(retangulos[i] < retangulos[i-1] && retangulo[i] < retangulos[i+1])
			//salva em pv como vale (+1)
			pv.push_back( make_pair(retangulos[i], 1) );
	}
	
	//qtd começa como 2
	int qtd, resp;
	qtd=resp=2;

	for(it=m.begin(); it!=m.end(); it++){
		//somo o que tiver na altura atual
		qtd+=it->second;
		
		//atualiza a resposta
		resp=max(resp, qtd);
	}
	
	//imprime a resposta
	printf("%d\n", resp);
}