Cod sursa(job #1374238)

Utilizator andrei_r_97Radoi Andrei andrei_r_97 Data 5 martie 2015 00:39:40
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>

#define MAX 500000
#define INF 30000

using namespace std;

int a[MAX];
int coadaD[MAX];

int main()
{
  FILE *in  = fopen("secventa.in", "r");
  FILE *out = fopen("secventa.out", "w");

  int n, k, i;
  fscanf(in, "%d %d", &n, &k);

  for (i = 0; i < n; i++) {
    fscanf(in, "%d", &a[i]);
  }

  int minim = (-1) * INF;
  int minStart = 0, minStop = 0;
  int Front = 1, Back = 0;
  for (i = 0; i < n; i++) {

    while (Front <= Back && a[i] < a[coadaD[Back]])
      Back--;

    coadaD[++Back] = i;

    if (coadaD[Front] == i - k)
      Front++;

    if (i + 1 >= k && a[coadaD[Front]] > minim) {
      minim = a[coadaD[Front]];
      minStart = i - k + 1;
      minStop = i;
    }

  }

  fprintf(out, "%d %d %d", minStart + 1, minStop + 1, minim);

  fclose(in);
  fclose(out);

  return 0;
}