Cod sursa(job #92162)

Utilizator the1dragonIonita Alexandru the1dragon Data 14 octombrie 2007 11:59:07
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>

int dq[512000], pos[512000];

int main()
{
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	int n, k, i, x, sol=0x80000000, ps, start=1, stop=1;
	scanf("%d %d", &n, &k);
	scanf("%d", &x);
	dq[start]=x;
	pos[start]=1;
	for (i=2; i<k; i++)
	{
		scanf("%d", &x);
		while ((pos[start]<=i-k) && (start<=stop)) ++start;
		while ((dq[stop]>=x) && (stop>=start)) --stop;
		++stop;
		dq[stop]=x;
		pos[stop]=i;
	}
	for (; i<=n; i++)
	{
		scanf("%d", &x);
		while ((pos[start]<=i-k) && (start<=stop)) ++start;
		while ((dq[stop]>=x) && (stop>=start)) --stop;
		++stop;
		dq[stop]=x;
		pos[stop]=i;
		if (dq[start]>sol)
			{sol=dq[start]; ps=i;}
	}
	printf("%d %d %d", ps-k+1, ps, sol);
	return 0;
}