Cod sursa(job #786166)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 10 septembrie 2012 16:38:49
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <stdio.h>
#include <fstream>
#include <list>
#include <climits>

using namespace std;

FILE *fout;
int maxEl, pos=0;
int N, K;

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

	indata >> N >> K;

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

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

	maxEl = secv[orderedElements.front()];
	orderedElements.pop_front();

	for (i = K; i < N; i ++){

		if(orderedElements.front() == i - K )
			orderedElements.pop_front();

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

		// when we are done with one iteration store the current min val
		if (secv[orderedElements.front()] > maxEl){
			maxEl = secv[orderedElements.front()];
			pos = i-K+1;
		}

	}
}

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

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

	process();
	store();

	return 0;
}