Cod sursa(job #404885)

Utilizator toniobFMI - Barbalau Antonio toniob Data 26 februarie 2010 20:53:08
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <deque>

using namespace std;
int N,K;
deque <pair<int,int> > D;

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