Cod sursa(job #716416)

Utilizator SmarandaMaria Pandele Smaranda Data 18 martie 2012 19:20:40
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.57 kb
#include<cstdio>
using namespace std;
long x[500001];
long q[500001];
int main () {
	long n,k,i,u,p,max=-1,inceput,sfarsit;
	
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	
	scanf("%ld%ld",&n,&k);
	for (i=1;i<=n;i++)
		scanf("%ld",&x[i]);
	u=0;
	p=1;
	for (i=1;i<=n;i++)  {
		while (p<=u && x[q[u]]>=x[i])
			u--;
		q[++u]=i;
		if (i-q[p]==k)
			p++;
		if (i>=k && q[u]-q[p]+1>=k)
			if (max<x[q[p]]) {
				max=x[q[p]];
				inceput=q[p];
				sfarsit=q[u];
			}
	}
	printf("%ld %ld %ld",inceput,sfarsit,max);
	return 0;
}