Cod sursa(job #474676)

Utilizator vladcatrinaVlad Catrina vladcatrina Data 4 august 2010 17:05:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <cstdio>
#include <fstream>
using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n,k,front,back,i,maxim,b1,b2;
int a[500010],d[500010];

int main(){
	
	maxim=-30001;
	
	fin>>n>>k;
	for(i=1;i<=n;i++){
		fin>>a[i];
	}
	
	front=1,back=0;
	
	for(i=1;i<=n;i++){
		
		while(front<=back && a[i]<=a[d[back]])
			back--;
		
		d[++back]=i;
			
		if(i>=k && a[d[front]]>maxim){
			maxim=a[d[front]];
			b1 = i-k+1;
			b2 = i;
			
		}
		if(d[front] <= i-k+1)
			front++;
	}
	
	fout<<b1<<" "<<b2<<" "<<maxim;
	
	return 0;
}