Cod sursa(job #424678)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 25 martie 2010 08:26:03
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<stdio.h>

int first=0, last=0;
struct asd{int val; int ind;};
asd stiva[500001];
int n,k,i,x, maxim=-31000, aux;

int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for(i=1;i<=n;i++)
	{
		scanf("%d", &x);
		if(first==0)
		{
			first=1;
			last=1;
			stiva[1].ind=1;
			stiva[1].val=x;
		}
		else 
		{
			while(stiva[first].ind<=i-k&&first<=last)
				first++;
			while(stiva[last].val>=x&first<=last)
				last--;
			stiva[++last].ind=i;
			stiva[last].val=x;
			if(i>=k&&stiva[first].val>maxim)
			{
				maxim=stiva[first].val;
				aux=i;
			}
		}


	}
	printf("%d %d %d\n", aux-k+1, aux, maxim);
	return 0;
}