Cod sursa(job #181946)

Utilizator alecmanAchim Ioan Alexandru alecman Data 20 aprilie 2008 07:54:57
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>

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

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

long Min, pMin, pMax, X, pInit, pFin;
long N, K;
long secv[ NMAX ], poz[ NMAX ];

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

void addBack(long V1, long V2)
{
  while(poz[ pFin ] != 0 && secv[ pFin ] > V1)
  {
    --pFin;
    if(pFin == -1)
      pFin = NMAX - 1;
  }
  
  ++pFin;

  if(pFin == NMAX)
    pFin = 0;

  secv[ pFin ] = V1;
  poz[ pFin ] = V2;

  if(poz[ pInit ] == 0)
    pInit = pFin;
}

void popFront(long V1)
{
  while(poz[ pInit ] != 0 && poz[ pInit ] <= V1 - K)
  {
    ++pInit;

    if(pInit == NMAX)
      pInit = 0;
  }
}

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

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

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

    if(i >= K)
    {
      if(Min < secv[ pInit ])
      {
	Min = secv[ pInit ];
	pMin = i - K + 1;
	pMax = i;
      }
    }
  }

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

int main()
{
  readValues();

  pInit = 0;
  pFin = 0;

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}