Cod sursa(job #183237)

Utilizator alecmanAchim Ioan Alexandru alecman Data 21 aprilie 2008 20:55:50
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<cstdio>
#include<deque>

using namespace std;

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

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

typedef struct secv
{
  int sec;
  long poz;
};

long N, K;
deque<secv> DQE;

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

void addBack(int V1, long V2)
{
  while(!DQE.empty() && DQE.back().sec > V1)
    DQE.pop_back();

  secv X;
  X.sec = V1;
  X.poz = V2;

  DQE.push_back(X);
}

void popFront(long V1)
{
  while(!DQE.empty() && DQE.front().poz <= V1 - K)
    DQE.pop_front();
}

void solveFunction()
{
  long Max = INFI, Pinit = -1;
  int X;

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

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

    if( i >= K)
    {
      if(Max < DQE.front().sec)
      {
        Max = DQE.front().sec;
	Pinit = i;
      }
    }
  }

  fprintf(fout, "%ld %ld %ld\n", Pinit - K + 1, Pinit, Max);
}

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}