Cod sursa(job #97795)

Utilizator piroslPiros Lucian pirosl Data 8 noiembrie 2007 19:36:47
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <stdlib.h>

int stack[500001];
int poz[500001];
int begin, end;

void add(int v, int pozitie)
{
	while(stack[end] > v && begin < end)
	{
		--end;
	}
	if(begin == end)
	{
		if(stack[end] > v) 
		{
			stack[end] = v;
		}
		else
		{
			stack[++end] = v;
		}
		poz[end] = pozitie;
	}
	else
	{
		stack[++end] = v;
		poz[end] = pozitie;
	}
}

void print()
{
	for(int i=begin;i<=end;++i)
		printf("(%d / %d) ", stack[i], poz[i]);
	printf("\n");
}


int main(void)
{
	FILE* fin;
	FILE* fout;
	fin = fopen("secventa.in", "r");
	fout = fopen("secventa.out", "w");
	int n, k;
	fscanf(fin, "%d %d\n", &n, &k);

	int max = -30001;
	int start = -1;
	begin = 0;
	end = 0;
	stack[0] = 300001;

	for(int i=0;i<n;++i)
	{
		int v;
		fscanf(fin, "%d ", &v);
		
		add(v, i);
		if(i>=k-1)
		{
		//	print();
			while(i-poz[begin] > k-1)
				++begin;
			if(stack[begin] > max)
			{
				max = stack[begin];
				start = i-(k-1);
			}
		}
	}
	fclose(fin);
	fprintf(fout, "%d %d %d\n", start+1, start+1+k-1, max);
	fclose(fout);
	return 0;
}