Cod sursa(job #399000)

Utilizator g3ppyStoian Vlad g3ppy Data 19 februarie 2010 18:51:04
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <deque>
#define NMAX 500005

#define llong long long

FILE *fin,*fout;

struct qq{
	int x,poz;
};

int n, k;

qq aux, ics;
qq a[NMAX];

int main()
{int i, min,start,stop,max,pozmin,first,last;

	fin = fopen ("secventa.in","rt");
	fout = fopen ("secventa.out","wt");
	
	fscanf(fin,"%d %d",&n,&k);
	fscanf(fin,"%d", &aux.x);
	first=last=0;
	aux.poz = 0;
	a[0] = aux;
	max = 0;
	
	for (i = 1; i < k; i++)
	{
		fscanf(fin,"%d", &aux.x);
		aux.poz = i;
		
		while (max >= 0 && a[last].x > aux.x)
		{
			last--;
			max --;
		}
		a[++last] = aux;
		max++;
		
	}
	
	min = a[first].x;
	pozmin = 0;
	
	for (i = k; i < n; i++)
	{
		fscanf(fin,"%d", &aux.x);
		aux.poz = i;
		
		if (a[first].poz <= i - k)
		{
			first++;
			max--;
		}
		
		
		while (max >= 0 && a[last].x > aux.x)
		{
			last--;
			max --;
		}
		a[++last] = aux;
		max++;
		
		if (min < a[first].x)
		{
			min = a[first].x;
			pozmin = i - k + 1;
		}
		
	}
	
	start = pozmin + 1;
	stop = pozmin +k;
	
	
	fprintf(fout,"%d %d %d\n",start,stop,min);
	fclose(fin);
	fclose(fout);	
return 0;	
}