Cod sursa(job #486888)

Utilizator dcm9000Dinu Cristian Mircea - UPB dcm9000 Data 23 septembrie 2010 01:09:07
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 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);

	fscanf(fisIn, "%d %d", &N, &K);
	for (int i=0; i<N; i++) fscanf(fisIn, "%d", V+i);

	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;
}