Cod sursa(job #1458448)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 7 iulie 2015 15:50:02
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <deque>

#define MAX_N 500000
#define INF 1000000000

std::deque <int> d;
int v[MAX_N];

int main(void) {
  FILE *f = fopen("secventa.in", "r");
  int n, k;
  int maxValue, maxPos;

  fscanf(f, "%d%d", &n, &k);

  for (int i = 0; i < (k - 1); i++) {
    fscanf(f, "%d", &v[i]);
    while (!d.empty() && v[d.back()] >= v[i]) {
      d.pop_back();
    }
    d.push_back(i);
  }

  maxPos = 0;
  maxValue = -INF;

  for (int i = k - 1; i < n; i++) {
    fscanf(f, "%d", &v[i]);
    while (!d.empty() && v[d.back()] >= v[i]) {
      d.pop_back();
    }
    d.push_back(i);
    if (d.front() <= i - k) {
      d.pop_front();
    }
    if (v[d.front()] > maxValue) {
      maxPos = i;
      maxValue = v[d.front()];
    }
  }

  fclose(f);

  f = fopen("secventa.out", "w");
  fprintf(f, "%d %d %d\n", maxPos - k + 2, maxPos + 1, maxValue);
  fclose(f);
  return 0;
}