Cod sursa(job #29620)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 9 martie 2007 17:47:56
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#include <string.h>
#include <stdlib.h>
FILE *f= fopen("secventa.in", "rt");
FILE *g = fopen("secventa.out", "wt");
int V[500010],
contor=0,deque[500010],primul=1,ultimul,N,K,max,PozInit,PozFin,poz[500010];

char s[10*500010];

int main()
{

fscanf(f,"%d %d ",&N,&K);
fgets(s, sizeof(s), f);
int n = strlen(s), k = 0, a = 0;
for (int i = 0; i < n; i++)
	if (s[i] == ' ') V[++k] = a, a = 0;
	else
            if ('0' <= s[i] && s[i] <= '9') a = a*10+(int)(s[i]-'0');
V[++k] = a;
for(int i=1;i<=K;i++)
    {int aux;
     aux = V[i];
    while(aux<deque[ultimul] && ultimul > 0)
       ultimul--;
    deque[++ultimul] = aux;
    poz[ultimul] = i;
    }
max=deque[primul];
PozInit=poz[primul];PozFin=poz[ultimul];
for(int i=K+1;i<=N;i++)
  {
  int aux;
  aux = V[i];
  if(poz[primul]<i-K+1)
    primul++;
  while(aux<deque[ultimul] && ultimul >= primul)
    ultimul--;
  deque[++ultimul] = aux;
  poz[ultimul] = i;
  if(max<deque[primul])
    {max=deque[primul];
    PozFin=i;
    }
  }
fprintf(g,"%d %d %d",PozFin-K+1,PozFin, max);
fclose(f);
fclose(g);
return 0;
}