Cod sursa(job #327979)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 30 iunie 2009 17:56:11
Problema Secv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define Nmax 12101
#define Inf 0x3f3f3f3f

int x[Nmax],n,nr,sol,i,j,xx;
vector<int> v,s;
int a[201000100];

int main()
{
	freopen("secv.in","r",stdin);
	freopen("secv.out","w",stdout);
	
	scanf("%d", &n);
	for (i=0;i<n;++i)
	{
		scanf("%d", &xx);
		v.push_back(xx);
	    s.push_back(xx);
	}
	
	
	sort(v.begin(),v.end());
	sol=Inf;
	a[v[0]]=1;
	nr=1;
	for (i=1;i<n;++i)
		 if (v[i]!=v[i-1])
		 {
			 nr++;
			 a[v[i]]=nr;
		 }
		 
	for (i=1;i<=nr;++i) x[i]=-Inf;
	
	for (i=1;i<=n;++i)
	{
		if (a[s[i]]==1) x[1]=i;
		else x[a[s[i]]]=x[a[s[i]]-1];
		sol=min(sol,i-x[nr]);
	}
	
	if (sol==Inf) printf("-1");
	else
	printf("%d", sol+1);
	
	return 0;
}