Cod sursa(job #1458438)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 7 iulie 2015 15:34:06
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <deque>

#define MAX_N 500000

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

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

  fscanf(f, "%d%d", &n, &k);
  minPos = 0;
  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);
  }
  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()] > v[minPos]) {
      minPos = d.front();
    }
  }
  fclose(f);

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