Cod sursa(job #460405)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 2 iunie 2010 14:49:16
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
using namespace std;
#define DIM 500002
#define INF 1<<20

int A[DIM], Deque[DIM];
int N, K, Bmin, Bpoz;
int i ,p ,u;

int main (){
	
	ifstream f1("secventa.in");
	ofstream f2("secventa.out");
	
	f1 >> N >> K;
	for (i=1; i<=N; i++) f1 >> A[i];
	
	p = 1; u = 0; Bmin = -INF;
	for (i=1; i<=N; i++){
		while (p <= u && A[i] <= A[Deque[u]])
			u--;
		Deque[++u] = i;
		if (Deque[p] == i-K)
			p++;
		if (i >= K && Bmin < A[Deque[p]]){
			Bmin = A[Deque[p]];
			Bpoz = i;		
		}
	}
	
	f2 << Bpoz-K+1 << " " << Bpoz << " " << Bmin;
	
	return 0;
}