Chuva

chuva.cpp

// Chuva - F1P2 - OBI 2016
// Rogério Júnior
// Complexidade: O(n)

#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 100100

int n, prefix[MAXN], suffix[MAXN], h[MAXN], resp;

int main(){
	
	// leio o valor de n e das alturas
	scanf("%d", &n);	
	for(int i=1;i<=n;i++) scanf("%d", &h[i]);
	
	// precaulculo os valores de prefix e suffix com a recursão mostrada
	for(int i=1;i<=n;i++) prefix[i]=max(prefix[i-1],h[i]);
	for(int i=n;i>=1;i--) suffix[i]=max(suffix[i+1],h[i]);
	
	// para cada seção da piscina
	for(int i=1;i<=n;i++)
		// se ela estiver debaixo d'água
		if(h[i]<min(prefix[i-1],suffix[i+1]))
			resp++;// incremento o valor de resp
	
	// por fim, imprimo o valor salvo em resp
	printf("%d\n", resp);
	
	return 0;
}