Cod sursa(job #786129)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 10 septembrie 2012 15:44:48
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <list>
#include <climits>

using namespace std;

struct elementInfo{
	int positionStart;
	int value;
};

void process(){
	ifstream indata("secventa.in");
	list<struct elementInfo> orderedElements;
	list<struct elementInfo> minVals;
	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 index = 0; index < length; index ++){

		if(index == 0)
			for(int i = index; i< index + 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 = index;

				orderedElements.push_back(newStruct);
			}
		else{
			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();
		tmpVal.positionStart = index;
		minVals.push_front(tmpVal);

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

	struct elementInfo maxEl;
	maxEl.value = INT_MIN;
	maxEl.positionStart = -1;

	while(!minVals.empty()){
		struct elementInfo element = minVals.front();

		if (element.value > maxEl.value){
			maxEl.value = element.value;
			maxEl.positionStart = element.positionStart;
		}

		minVals.pop_front();
	}

	int maxValue = maxEl.value;
	int start = maxEl.positionStart + 1;
	int end = maxEl.positionStart + K ;

	// store the results
	freopen("secventa.out","w",stdout);
	printf("%d %d %d",start,end,maxValue);
}

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

	process();

	return 0;
}