Cod sursa(job #404864)

Utilizator toniobFMI - Barbalau Antonio toniob Data 26 februarie 2010 20:23:44
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <cstdio>
#include <deque>
using namespace std;
const int NMax=5000002;

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

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;
		}
	}
	printf("%lld %lld %lld",inceput,inceput+K-1,Max);
	return 0;
}