Cod sursa(job #314575)

Utilizator wazupPricop Mircea wazup Data 12 mai 2009 09:40:11
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
using namespace std;
#include <deque>
#include <stdio.h>
FILE *fin,*fout;
struct el { int val, ind; };
deque<el> v;
long a[500001],n,k,secstart,i,minall,mins,minf;

void addtoq(int valt, int indt)
{
	el toadd;
	toadd.val = valt;
	toadd.ind = indt;
	
	if (v.empty())
	{ 
        v.push_back(toadd); 
	    return; 
	}
	
	while (!v.empty()&&v.back().val>valt) v.pop_back();
	v.push_back(toadd);
	while (!v.empty()&&v.front().ind<secstart) v.pop_front();
}

int main()
{
	fin = fopen("secventa.in","rt");
	fout = fopen("secventa.out","wt");
	fscanf(fin,"%ld %ld\n",&n, &k);
	for (i=0;i<n;i++)
		fscanf(fin,"%ld ",&a[i]);
	secstart = 0;
	for (i=0;i<k;i++)
		addtoq(a[i],i);
	minall = v.front().val;
	for (secstart = 1; secstart<n-k+1;secstart++)
	{
		addtoq(a[secstart+k-1],secstart+k-1);
		if (v.front().val>minall) { minall = v.front().val; mins = secstart+1; minf=secstart+k; }
	}
	fprintf(fout,"%ld %ld %ld\n",mins,minf,minall);
}