Cod sursa(job #975324)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 19 iulie 2013 19:50:57
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>
using namespace std;

#define NMAX 500001

int i, N, K, Q;
int Start = 1, End;
int st, dr, ANS = -30001;

int v[NMAX];
int Deque[NMAX];

void Insert(int i) {
	while (Start <= End && v[i] <= v[Deque[End]]) --End;
	Deque[++End] = i;
}

int Query(int p) {
	while (Start <= End && Deque[Start] < p) ++Start;
	return v[Deque[Start]];
}

int main() {
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%i%i", &N, &K);
	for (i = 1; i <= N; ++i) {
		scanf("%i", &v[i]);
		Insert(i);
		if (i >= K) {
			Q = Query(i - K + 1);
			if (Q > ANS) 
				ANS = Q, st = i - K + 1, dr = i;
		}
	}
	printf("%i %i %i\n", st, dr, ANS);
	return 0;
}