Cod sursa(job #1458458)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 7 iulie 2015 16:00:38
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <deque>
#include <ctype.h>

#define MAX_N 500000
#define INF 30001
#define BUFFSIZE 4096

std::deque <int> d;    // deque pentru indici minimi
short v[MAX_N];        // valori
char buffer[BUFFSIZE]; // buffer pentru citire
int pos = BUFFSIZE;    // pozitia in buffer

inline char getChar(FILE *f) {
  if (pos == BUFFSIZE) {
    fread(buffer, 1, BUFFSIZE, f);
    pos = 0;
  }
  return buffer[pos++];
}

inline void readShort(short *x, FILE *f) {
  char c;
  bool sign = 0;

  do {
    c = getChar(f);
    sign = (sign || (c == '-'));
  } while (!isdigit(c));

  *x = 0;
  do {
    *x = (*x << 1) + (*x << 3) + (c - '0');
    c = getChar(f);
  } while (isdigit(c));

  *x ^= ((*x ^ -*x) & -sign);
}

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

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

  for (register int i = 0; i + 1 < k; i++) {
    readShort(&v[i], f);
    while (!d.empty() && v[d.back()] >= v[i]) {  // pentru i < j, j scoate din deque toti i care definesc un v[i] >= v[j]
      d.pop_back();
    }
    d.push_back(i);
  }

  maxPos = 0;
  maxValue = -INF;

  for (register int i = k - 1; i < n; i++) {
    readShort(&v[i], f);
    while (!d.empty() && v[d.back()] >= v[i]) {
      d.pop_back();
    }
    d.push_back(i);
    if (d.front() <= i - k) {                    // nu mai face parte din secventa curenta
      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;
}