Cod sursa(job #398836)

Utilizator g3ppyStoian Vlad g3ppy Data 19 februarie 2010 15:17:01
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <algorithm>
#include <deque>
#define NMAX 500005

#define llong long long

using namespace std;

FILE *fin,*fout;

struct qq{
	int x,poz;
};

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.back().x > aux.x)
		{
			a.pop_back();
			max --;
		}
		a.push_back(aux);
		max++;
		
	}
	
	min = a.front().x;
	pozmin = 0;
	
	for (i = k; i < n; i++)
	{
		fscanf(fin,"%d", &aux.x);
		aux.poz = i;
		
		if (a.front().poz <= i - k)
		{
			a.pop_front();
			max--;
		}
		
		
		while (max >= 0 && a.back().x > aux.x)
		{
			a.pop_back();
			max --;
			ics = a.back();
		}
		a.push_back(aux);
		max++;
		
		if (min < a.front().x)
		{
			min = a.front().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;	
}