Cod sursa(job #786058)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 10 septembrie 2012 14:21:22
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <stack>
#include <climits>

using namespace std;

struct elementInfo{
	int position;
	int value;
};

void process(){
	ifstream indata("secventa.in");
	stack<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 index = 0; index < length; index ++){
//		cout << "iteration " << index << endl;

		if(index == 0)
			for(int i = index; i< index + K; i ++ ){
				// check whether the current element is smaller
				//	than the last element in the stack
				while(!orderedElements.empty() &&
						secv[i] < orderedElements.top().value
				){
//					cout << "removing " << orderedElements.top().value << endl;
					orderedElements.pop(); // remove the last element

				}

				struct elementInfo newStruct;
				newStruct.value = secv[i];
				newStruct.position = i;

				orderedElements.push(newStruct);
//				cout <<" adding element " << secv[i] << endl;
			}
		else{
			int location =  K + index - 1;
//			cout << "Index " << index << " Stack size " << orderedElements.size() << endl;

			// check whether the current element is smaller
			//	than the last element in the stack
			while(!orderedElements.empty() &&
					secv[location] < orderedElements.top().value
			){
				if(orderedElements.top().position < index)
					break;
//				cout << "removing " << orderedElements.top().value << endl;
				orderedElements.pop(); // remove the last element

			}

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

			orderedElements.push(newStruct);
//			cout <<" adding element " << secv[location] << endl;
		}


//		cout <<endl;
	}

	struct elementInfo maxEl;
	maxEl.value = INT_MIN;
	maxEl.position = 0;

	while(!orderedElements.empty()){
		struct elementInfo element = orderedElements.top();
//		cout << element.value << " ";

		if(element.position > N -K +1){
			orderedElements.pop();
			continue;
		}

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

		orderedElements.pop();
	}

//	cout << endl;

	int maxValue = maxEl.value;
	int start = maxEl.position + 1;
	int end = maxEl.position + 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;
}