Cod sursa(job #1092241)

Utilizator veleanduAlex Velea veleandu Data 26 ianuarie 2014 19:20:44
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <iostream>
using namespace std;

const int kMaxN = 500005;

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

int el[kMaxN], deq[kMaxN];

int main() {
	int n, k;
	in >> n >> k;
	for (int i = 1; i <= n; ++i)
		in >> el[i];
	int st = 1;
	int dr = 0;
	for (int i = 1; i < k; ++i) {
		while (dr >= st and el[deq[dr]] >= el[i])
			--dr;

		deq[++dr] = i;
	}
	int mx = -0x3f3f3f3f, p;
	for (int i = k; i <= n; ++i) {
		if (deq[st] == i - k)
			++st;

		while (dr >= st and el[deq[dr]] >= el[i])
			--dr;

		deq[++dr] = i;
		if (mx < el[deq[st]]) {
			p = i;
			mx = el[deq[st]];
		}
	}
 	out << p - k + 1 << ' ' << p << ' ' << mx << '\n';
	return 0;
}