Cod sursa(job #341152)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 17 august 2009 17:19:23
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<cstdio>
#define N 500001
#include<algorithm>
using namespace std;
int n,k,v[N],p,u,miin,sf,inc,d[N];
void citire()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d",&n,&k);
	for (int i=1; i<=k; ++i)
	{
		scanf("%d",&v[i]);
		while (p!=u&&v[i]<v[d[u-1]])
			--u;
		d[u++]=i;
	}
	miin=v[d[p]];
	inc=1;sf=k;
	for (int i=k+1; i<=n; ++i)
	{
		scanf("%d",&v[i]);
		int g=i-d[p];
		if (g==k)
			++p;
		while (u!=p&&v[i]<v[d[u-1]])
			--u;
		d[u++]=i;
		if (miin<v[d[p]])
		{
			miin=v[d[p]];
			inc=d[p];
			sf=d[u-1];
		}
	}
	printf("%d %d %d",inc,sf,miin);
}

int main()
{
	citire();
	
	return 0;
}