Solução OBI 2017

papel.cpp

// Ivan Carvalho
// Cortando o Papel - Fase 2 Programação Nível 2 - OBI 2017
// O(n*log(n))
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
vector<ii> papel;
int estado[100010],n,tiras,resp;
int main(){
	scanf("%d",&n);
	tiras = 1;
	resp = 1;
	for(int i=1;i<=n;i++){
		estado[i] = 1;
		int hi;
		scanf("%d",&hi);
		papel.push_back(ii(hi,i));
	}
	sort(papel.begin(),papel.end());
	for(int i=0;i<n;i++){
		int pos = papel[i].second;
		estado[pos] = 0;
		if(estado[pos-1] == 1 && estado[pos+1] == 1) tiras++;
		if(estado[pos-1] == 0 && estado[pos+1] == 0) tiras--;
		if(i == n-1 || papel[i].first != papel[i+1].first){
			resp = max(resp,tiras);
			//printf("C %d\n",tiras);
		}
	}
	printf("%d\n",resp+1);
	return 0;
}