Cod sursa(job #786156)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 10 septembrie 2012 16:21:58
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <list>
#include <climits>

using namespace std;
FILE *fout;

struct elementInfo{
	int positionStart;
	int value;
};

void process(){
	ifstream indata("secventa.in");
	list<struct elementInfo> orderedElements;
	int secv[500000];

	int N, K;
	indata >> N >> K;
	int length = N-K+1;

	for(int i =0; i< N; i++)
		indata >> secv[i];

	for(int i = 0; i<  K; i ++ ){
		while(!orderedElements.empty() &&
				secv[i] < orderedElements.back().value)
			orderedElements.pop_back() ; // remove the last element

		struct elementInfo newStruct;
		newStruct.value = secv[i];
		newStruct.positionStart = 0;

		orderedElements.push_back(newStruct);
	}

	struct elementInfo maxEl = orderedElements.front();
	orderedElements.pop_front();

	for (int index = 1; index < length; index ++){

		int location =  K + index -1;

		while(!orderedElements.empty() &&
				secv[location] < orderedElements.back().value)
			orderedElements.pop_back(); // remove the last element

		struct elementInfo newStruct;
		newStruct.value = secv[location];
		newStruct.positionStart = location;

		orderedElements.push_back(newStruct);

		// when we are done with one iteration store the current min val
		struct elementInfo tmpVal = orderedElements.front();
		if (tmpVal.value > maxEl.value){
			maxEl.value = tmpVal.value;
			maxEl.positionStart = index;
		}

		if(orderedElements.front().positionStart <= index )
			orderedElements.pop_front();
	}

	// store the results
	fout=fopen("secventa.out","w");
	fprintf(fout,"%d %d %d",maxEl.positionStart + 1,
			maxEl.positionStart + K ,
			maxEl.value);
	fclose(fout);

}

int main(int argc, char* argv[]) {

	process();

	return 0;
}