Cod sursa(job #398829)

Utilizator g3ppyStoian Vlad g3ppy Data 19 februarie 2010 14:56:43
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <stdio.h>
#include <algorithm>
#include <deque>
#define NMAX 500005

#define llong long long

using namespace std;

FILE *fin,*fout;

struct qq{
	int poz,x;
};

int n, k;

qq aux, ics;

deque<qq> a;

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

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