Cod sursa(job #806886)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 3 noiembrie 2012 18:01:31
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>

using namespace std;

#define Nmax 500001

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

int V[Nmax], Deque[Nmax], N, k, st, dr, poz, minim;

int main() {
	
	int i;
	
	f>>N>>k;
	
	f>>V[1];
	st = dr = 1;
	Deque[st] = 1;
	minim = -1<<30;
	
	for(i=2; i<=N; i++) {
		f>>V[i];
		
		while(V[i] <= V[Deque[dr]] && st<=dr)
			dr--;
		// sterg din deque toate elem mai mari ca V[i] formand mereu in felul asta un sir crescator in deque
		
		Deque[++dr] = i;
		// adaug pozitia elementului curent
		
		while(Deque[st]+k <= i)
			st++;
		
		if(minim < V[Deque[st]] && i>=k) {
			minim = V[Deque[st]];
			poz = i;
		}
	}
	
	g<<poz-k+1<<" "<<poz<<" "<<minim<<"\n";
	
	f.close();
	g.close();
	
	return 0;
}