Cod sursa(job #181945)

Utilizator alecmanAchim Ioan Alexandru alecman Data 20 aprilie 2008 07:39:18
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>

#define INPUT "secventa.in"
#define OUTPUT "secventa.out"
#define INFI -2000000000

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

typedef struct List
{
  long value, poz;
  List *next, *prev;
};

List *left, *right;

long Min, pMin, pMax, X;
long N, K;

void readValues()
{
  fscanf(fin, "%ld %ld", &N, &K);
}

void addBack(long V1, long V2)
{
  List *adr;

  if(left != NULL)
    while(right != NULL && right -> value > V1)
      right = right -> prev;
  
  adr = new List;
  adr -> value = V1;
  adr -> poz = V2;
  adr -> prev = right;
  adr -> next = NULL;
  right -> next = adr;
  if(left == NULL)
    left = left -> next;
  right = right -> next;
}

void popFront(long V1)
{
  if(left != NULL)
    while(left -> poz <= V1 - K)
      left = left -> next;
}

void solveFunction()
{
  left = NULL;
  Min = INFI;
  pMin = -1;
  pMax = -1;
  right = left;

  for(long i = 1; i <= N; ++i)
  {
    fscanf(fin, "%ld", &X);

    addBack(X, i);
    popFront(i);

    if(i >= K)
    {
      if(Min < left -> value)
      {
        Min = left -> value;
	pMin = i - K + 1;
	pMax = i;
      }
    }
  }

  fprintf(fout, "%ld %ld %ld\n", pMin, pMax, Min);
}

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}