Cod sursa(job #486890)

Utilizator dcm9000Dinu Cristian Mircea - UPB dcm9000 Data 23 septembrie 2010 01:21:15
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

#define FILE_IN "secventa.in"
#define FILE_OUT "secventa.out"

int N,K;
int V[500000];
int Q[500000];

int main()
{
	FILE* fisIn = fopen(FILE_IN, "r");
	ofstream fisOut(FILE_OUT);

	static char linie[3600000];
	fscanf(fisIn, "%d %d", &N, &K);
	fgets(linie, 3600000, fisIn);
	fgets(linie, 3600000, fisIn);

	char* ptr = linie;
	char* ptr2;
	for (int i=0; i<N; i++)
	{
		V[i] = strtol(ptr, &ptr2, 10);
		ptr = ptr2;
	}
	
	int best;
	int start;
	int* l = Q;
	int* r = Q;
	for (int i=0; i<K; i++)
	{
		int elem = V[i];
		while ((l!=r) && (V[*(r-1)] >= elem)) r--;
		*(r++) = i;
	}
	
	best = V[*l];
	start = 0;
	
	for (int i=K; i<N; i++)
	{
		while ((l!=r) && (*l <= i-K)) l++;
		int elem = V[i];
		while ((l!=r) && (V[*(r-1)] >= elem)) r--;
		*(r++) = i;

		if (V[*l] > best)
		{
			best = V[*l];
			start = i-K+1;
		}
	}

	fisOut << (start+1) << " " << (start+K) << " " << best;
}