Cod sursa(job #16452)

Utilizator vlad_DVlad Dumitriu vlad_D Data 13 februarie 2007 05:03:17
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <set>

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 true;
	if (a.val == b.val && a.id < b.id) return true;
	return false;
	}
set<nod> HEAP;
int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	
	scanf("%d %d", &N, &K);
	int sol = -31111, left;
	HEAP.insert(nod(0, 0));
	for (i=1; i<=N; i++) {
		scanf("%d", &v[i]);
		HEAP.insert(nod(v[i], i));
		if (i>=K) {
			//nod best = *HEAP.find(nod(v[i-K+1], i-K+1));
			nod best;
			HEAP.erase(HEAP.find(nod(v[i-K], i-K)));
			best = *HEAP.begin();
			//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