Cod sursa(job #183226)

Utilizator alecmanAchim Ioan Alexandru alecman Data 21 aprilie 2008 20:52:21
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");

long N, K;
deque<int> secv;
deque<long> poz;

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

void addBack(int V1, long V2)
{
  while(!secv.empty() && secv.back() > V1)
  {
    secv.pop_back();
    poz.pop_back();
  }

  secv.push_back(V1);
  poz.push_back(V2);
}

void popFront(long V1)
{
  while(!secv.empty() && poz.front() <= V1 - K)
  {
    secv.pop_front();
    poz.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 < secv.front())
      {
        Max = secv.front();
	Pinit = i;
      }
    }
  }

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

int main()
{
  readValues();

  solveFunction();

  fclose(fin);
  fclose(fout);

  return 0;
}