Cod sursa(job #1595904)

Utilizator stoianmihailStoian Mihail stoianmihail Data 10 februarie 2016 17:05:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <limits.h>
#include <stdio.h>
#include <ctype.h>
#include <vector>
#include <queue>

using std::priority_queue;
using std::vector;

#define Dragoste 4096

typedef struct {
  int v, pos;
} pair;

typedef struct {
  bool operator()(const pair &X, const pair &Y) {
    return (X.v > Y.v);
  }
} minHeap;

priority_queue <pair, vector <pair>, minHeap> heap;

int N, K;
int pos = Dragoste;
char c, sign, buff[Dragoste];

/** Da-mi urmatorul caracter. **/
char getChar(FILE *f) {
  if (pos == Dragoste) {
    fread(buff, 1, Dragoste, f);
    pos = 0;
  }
  return buff[pos++];
}

/** Da-mi urmatorul numar din fisier. **/
int freef(FILE *f) {
  int result = 0;
  c = '#';

  do {
    sign = c;
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return (sign == '-') ? -result : result;
}

int main(void) {
  pair base;
  int i, lim, low, max = INT_MIN, end;
  FILE *f = fopen("secventa.in", "r");

  /* Citirea datelor si calcularea solutiei. */
  N = freef(f), K = freef(f);
  for (lim = K - 1, i = 0; i < lim; i++) {
    heap.push({freef(f), i});
  }
  for (; i < N; i++) {
    heap.push({freef(f), i});

    /* Lazy - deletion. */
    low = i - lim;
    for (base = heap.top(); base.pos < low; heap.pop(), base = heap.top());
    if (base.v > max) {
      max = base.v;
      end = i;
    }
  }
  fclose(f);

  /* Afisarea solutiei. */
  freopen("secventa.out", "w", stdout);
  fprintf(stdout, "%d %d %d\n", end - K + 2, end + 1, max);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}