Cod sursa(job #1503688)

Utilizator ArkinyStoica Alex Arkiny Data 16 octombrie 2015 19:04:42
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
#include<deque>

FILE *in,*out;
int d[500001], v[500001], st_d=1, f_d=1,st_v=1,f_v=1;

int N, K;

int main()
{
	in = fopen("secventa.in", "r");
	out = fopen("secventa.out", "w");

	fscanf(in, "%d%d", &N, &K);
	int e,l,min=1<<31,left=0,right=0;
	for (int i = 1;i <= N;++i)
	{
		fscanf(in, "%d", &e);
		while (st_d!=f_d && e <d[f_d-1])
		{
			--f_d;
			--f_v;
		}
		d[f_d++] = e;
		v[f_v++] = i;
		if (i >= K)
		{
			if (d[st_d] > min)
			{
				min=d[st_d];
				left = i-K+1;
				right =i ;
			}
			if (v[st_v] == i-K+1)
			{
				++st_d;
				++st_v;
			}
		}
	}
	fprintf(out,"%d %d %d",left,right,min);
	return 0;
}