Cod sursa(job #2101037)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 6 ianuarie 2018 18:52:08
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>
#include <cctype>
#include <deque>

const int MAXN = 5e5;
const int INF = 2e9;
#define BUF_SIZE 1 << 14

char buf[BUF_SIZE];
int v[MAXN], pos = BUF_SIZE;
std::deque <int> dq;

inline char nextch(FILE *f) {
  if (pos == BUF_SIZE) {
    fread(buf, BUF_SIZE, 1, f);
    pos = 0;
  }
  return buf[pos++];
}

inline int nextnum(FILE *f) {
  int x = 0, sign;
  char ch = nextch(f);
  while (!isdigit(ch) && ch != '-') {
    ch = nextch(f);
  }
  sign = 1;
  if (ch == '-') {
    sign = -1;
    ch = nextch(f);
  }
  while (isdigit(ch)) {
    x = 10 * x + ch - '0';
    ch = nextch(f);
  }
  return x * sign;
}

int main() {
  int n, k, ans, r;
  FILE *f = fopen("secventa.in", "r");
  n = nextnum(f), k = nextnum(f);
  for (int i = 0; i < n; ++i) {
    v[i] = nextnum(f);
  }
  fclose(f);
  ans = -INF;
  for (int i = 0; i < n; ++i) {
    if (i - k == dq.front()) {
      dq.pop_front();
    }
    while (!dq.empty() && v[dq.back()] > v[i]) {
      dq.pop_back();
    }
    dq.push_back(i);
    if (i >= k - 1 && ans < v[dq.front()]) {
      ans = v[dq.front()];
      r = i;
    }
  }
  f = fopen("secventa.out", "w");
  fprintf(f, "%d %d %d\n", r - k + 2, r + 1, ans);
  fclose(f);
  return 0;
}