Cod sursa(job #461976)

Utilizator toniobFMI - Barbalau Antonio toniob Data 9 iunie 2010 14:53:10
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
using namespace std;

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

int deq[500001], v[500001], st = 1, dr, st_afis = 1, dr_afis = 1, maxx, n, k;
char s[5000003];

void citire () {
	in >> n >> k >> ws;
	freopen("secventa.in","r",stdin);
	scanf("%d%d\n",&n,&k);
	//in.getline (s, 5000003);
	gets(s);
	int val = 0, semn = 1;
	for (int i = 0; s[i] && s[i]!='\n' ; ++i) {
		if (s[i] == '-') {
			semn = -1;
			
			continue;
		}
		
		if (s[i] == ' ') {
			v[++v[0]] = val * semn;
			val = 0;
			semn = 1;
			
			continue;
		}
		
		val = val * 10 + (s[i] - '0');
	}
	if (v[0] < n) {
		v[n] = val * semn;
	}
}

inline void stanga (int i) {
	if (deq[st] == i - k) {
		++st;
	}
}

void dreapta (int i) {
	for (; st <= dr && v[i] <= v[deq[dr]]; --dr) { }
	deq[++dr] = i;
}

void verif (int i) {
	if (i < k) {
		return;
	}
	
	if (v[deq[st]] > maxx) {
		st_afis = i - k + 1;
		dr_afis = i;
		maxx = v[deq[st]];
	}
}

int main () {
	citire ();
	
	for (int i = 1; i <= n; stanga (i), dreapta (i), verif (i), ++i) { }
	
	out << st_afis << ' ' << dr_afis << ' ' << maxx << '\n';
	
	return 0;
}