Cod sursa(job #750226)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 21 mai 2012 16:00:04
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<iostream>
#include<fstream>

using namespace std;

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

int a[500010], q[500010];
int N, k, i, st, dr, rez, poz;

int main()
{	
	in >> N >> k;
	
	for(i = 1; i <= N; ++i)
		in >> a[i];
	
	rez = ~(1 << 30);
	st = 1, dr = 0;
	
	for(i = 1; i <= k - 1; ++i){
		while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
		dr++;
		q[dr] = i;
	}
	
	for(i = k; i <= N; ++i){
		while((st <= dr) && (a[i] <= a[ q[dr] ])) dr--;
		dr++;
		q[dr] = i;
		
		while((st <= dr) && (q[st] < (i - k + 1))) st++;
		
		if(a[ q[st] ] > rez){
			rez = a[ q[st] ];
			poz = i;
		}
	}
	
	out << poz - k + 1 << " " << poz << " " << rez;
	
	return 0;
}