Cod sursa(job #786175)

Utilizator dogDaysAreOverAndreea Gheorghe dogDaysAreOver Data 10 septembrie 2012 16:52:39
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <stdio.h>
#include <fstream>
#include <list>

#define MAX 500005

using namespace std;

FILE *fout, *fileread;
int maxEl=-35000, pos=0 ;
int N, K;
int secv[MAX];
char numbers[MAX];

void quickFileRead(){
	int j=0, order;
	fileread = fopen("secventa.in", "r");
	fscanf(fileread, "%d %d\n", &N, &K);
	fgets(numbers, sizeof(numbers), fileread);

	for(int i =0; i< N; i++){
		secv[i]=0;
		order = 0;

		while(numbers[j]!='-' &&
				(numbers[j]<'0' || numbers[j]> '9'))
			j++;

		if(numbers[j]=='-'){
			order = 1;
			j++;
		}
		while(numbers[j]>='0' && numbers[j]<='9'){
			secv[i]=secv[i]*10+(numbers[j]-'0');
			j++;
		}

		if(order)
			secv[i] =-secv[i];
	}

	fclose(fileread);
}

void process(){
	ifstream indata("secventa.in");
	list<int> orderedElements;
	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()];

	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[]) {

	quickFileRead();
	process();
	store();

	return 0;
}