Cod sursa(job #16453)

Utilizator vlad_DVlad Dumitriu vlad_D Data 13 februarie 2007 05:07:43
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
/*
secventa de pe infoarena... sursa cu priority_queue a luat:

cu set ia numa: 40


*/
#include <cstdio>
#include <queue>

using namespace std;
int N, K, i, j;
int v[500001];
struct nod{
	int val, id;
	nod(int _v, int _i) {val = _v; id = _i;};
	nod(){};
	};
bool operator<(const nod &a, const nod &b){
	if (a.val < b.val) return false;
	if (a.val == b.val && a.id < b.id) return false;
	return true;
	}
priority_queue<nod> HEAP;
int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	
	scanf("%d %d", &N, &K);
	int sol = -31111, left;
	HEAP.push(nod(0, 0));
	for (i=1; i<=N; i++) {
		scanf("%d", &v[i]);
		HEAP.push(nod(v[i], i));
		if (i>=K) {
			//nod best = *HEAP.find(nod(v[i-K+1], i-K+1));
			nod best;
			while (1){
				best = HEAP.top();
	//			printf("%d %d\n", best.id, best.val);
				if (best.id >= i-K+1) break;
				HEAP.pop();
				}

			//printf("%d %d \n", best.val, best.id);
			if (best.val > sol) {sol = best.val; left = i - K + 1;}
			}
		}
	printf("%d %d %d\n", left, left+K-1, sol);
	return 0;
}
//-1 2 3 1 0 4 8 6