Cod sursa(job #404879)

Utilizator toniobFMI - Barbalau Antonio toniob Data 26 februarie 2010 20:35:08
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <deque>
using namespace std;
const int NMax=500002;
const int MaxMax=-1000000000;

deque <int> D;
int N,K,v[NMax];
long long Max=MaxMax,inceput,sfarsit;

int main(){
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d",&N,&K);
	int i;
	for(i=1;i<=N;++i){
		scanf("%d",v+i);
	}
	for(i=1;i<K;++i){
		for(;!D.empty() && v[D.back()]>=v[i];D.pop_back()){}
		D.push_back(i);
	}
	for(;i<=N;++i){
		for(;!D.empty() && v[D.back()]>=v[i];D.pop_back()){}
		D.push_back(i);
		if(D.front()<=i-K){
			D.pop_front();
		}
		if(v[D.front()]>=Max){
			Max=v[D.front()];
			inceput=i-K+1;
			sfarsit=K;
		}
	}
	printf("%lld %lld %lld",inceput,sfarsit+inceput-1,Max);
	return 0;
}