Cod sursa(job #114060)

Utilizator scvalexAlexandru Scvortov scvalex Data 12 decembrie 2007 16:32:05
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <iostream>
#include <fstream>
#include <map>

using namespace std;

int N(0),
	K(0);

short a[500000],
	  h[500000];

map<int, int> whereis;

#define XCHG(a, b) {int t = a; a = b; b = t;}

void print_heap() {
	cout << "Heap of size " << h[0] << ": ";
	for (int i(1); i <= h[0]; ++i)
		cout << h[i] << " ";
	cout << endl;
	for (map<int, int>::const_iterator it = whereis.begin(); it != whereis.end(); ++it)
		cout << "Element\t" << it->first << " is at pos\t" << it->second << endl;
}

void raise(int pos) {
	while ((pos > 1) && (h[pos] < h[pos / 2])) {
		XCHG(h[pos], h[pos / 2]);
		XCHG(whereis[h[pos]], whereis[h[pos / 2]]);
		pos /= 2;
	}
}

void lower(int pos) {
	while (true) {
		int max = pos;
		if ((2*pos <= h[0]) && (h[2*pos] < h[max]))
			max = 2*pos;
		if ((2*pos + 1 <= h[0]) && (h[2*pos + 1] < h[max]))
			max = 2*pos + 1;
		if (h[max] != h[pos]) {
			XCHG(h[pos], h[max]);
			XCHG(whereis[h[pos]], whereis[h[max]]);
			pos = max;
		} else
			break;
	}
}

void insert_into_heap(int v) {
	++h[0];
	h[h[0]] = v;
	whereis.insert(pair<int, int>(v, h[0]));
	raise(h[0]);
}

void remove_from_heap(int v) {
	int pos = whereis[v];
	whereis.erase(v);
	if (pos != h[0]) {
		h[pos] = h[h[0]];
		--h[0];
		whereis[h[pos]] = pos;
		raise(pos);
		lower(pos);
	} else
		--h[0];
}

int main(int argc, char *argv[]) {
	ifstream fin("secventa.in");
	fin >> N >> K;
	for (int i(0); i < N; ++i)
		fin >> a[i];
	fin.close();

	int i(0);
	for (i = 0; i < K; ++i)
		insert_into_heap(a[i]);

	int maxi(0);
	int max(-666);
	for (; i < N; ++i) {
		if ((h[1] > max) || (max == -666)) {
			max = h[1];
			maxi = i - K + 1;
//			cout << max << endl;
		}
		remove_from_heap(a[i - K]);
		insert_into_heap(a[i]);
//		print_heap();
	}

	if ((h[1] > max) || (max == -666)) {
		max = h[1];
		maxi = i - K;
//		cout << max << endl;
	}

	ofstream fout("secventa.out");
	fout << maxi + 1 << " " << maxi + K << " " << max << endl;
	fout.close();

	return 0;
}