Cod sursa(job #1503702)

Utilizator ArkinyStoica Alex Arkiny Data 16 octombrie 2015 19:32:41
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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;
char c[3000101];
int N, K;

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

	fscanf(in,"%d%d", &N, &K);
	fgetc(in);
	fgets(c, 3000101, in);
	int e,l,min=1<<31,left=0,right=0,c_s=0,sgn;
	for (int i = 1;i <= N;++i)
	{
		e = 0;
		sgn = 1;
		while (c[c_s] != ' ' && c[c_s] != '\0')
		{
			if (c_s == '-')
				sgn = -1;
			else
				e = e * 10 + c[c_s] - '0';
			++c_s;
		}
		++c_s;
		e = e*sgn;
		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;
}