Cod sursa(job #16454)

Utilizator vlad_DVlad Dumitriu vlad_D Data 13 februarie 2007 05:26:33
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
/*
problema secventa infoarena.ro
implementare: deque
testat:
RMQ: 70 pct
heap_cu_set: 40 pct
heap_cu_priority_queue: 80 pct
*/
#include <cstdio>
#include <deque>


using namespace std;
int N, K, i, j;
struct nod{
	int val, id;
	nod(int _v, int _i) {val = _v; id = _i;};
	nod(){};
};
deque<nod> Q;
int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%d %d", &N, &K);
	int sol = -32222, left;
	for (i=1; i<=N; i++) {
		int X;
		scanf("%d", &X);
		//X se duce la dreapta
		//scot din dreapta tot ce este mai mare ca X 
		while (!Q.empty()) {
			nod A = Q.back();
			if (A.val > X) Q.pop_back();
			else break;
		}
		Q.push_back(nod(X, i));
		//baga in dreapta X
		//scoate din stanga tot ce este mai batran de K pasi
		while (!Q.empty()) {
			nod A = Q.front();
			if (A.id < i - K + 1) Q.pop_front();
			else break;
			}
		nod A = Q.front();
		if (A.val > sol) {left = i - K +1; sol = A.val;}
		}
printf("%d %d %d\n", left, left+K-1, sol);
return 0;
}