Cod sursa(job #97852)

Utilizator piroslPiros Lucian pirosl Data 9 noiembrie 2007 01:36:46
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <stdlib.h>

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

void add(int& v, int& pozitie)
{
	while(stack[end] >= v && begin < end)
	{
		--end;
	}
	
	if(stack[end] >= v) 
	{
		stack[end] = v;
	}
	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)
		{
			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;
}