Cod sursa(job #1506159)

Utilizator juniorOvidiu Rosca junior Data 20 octombrie 2015 05:58:23
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>

using namespace std;

int maxt, i, k, minv, d, a[500001], n, c1, c2, b[500001], s, l[500001];
ifstream f ("secventa.in");
ofstream g ("secventa.out");

int main() {
  f >> n >> k;
  for (i = 1; i <= n; i++)
    f >> a[i];
  s = 1; d = 1; maxt = -30001; b[1] = a[1]; l[s] = 1;
  for (i = 2; i <= n; i++) {
    while (a[i] <= b[d] and d >= s)
      d--;
    d++;
    b[d] = a[i]; l[d] = i;
    if (i - l[s] == k)
      s++;
    if (k <= i)
      if (b[s] > maxt) {
        c1 = i - k + 1; c2 = i; maxt = b[s];
      }
  }
  g << c1 << " " << c2 << " " << maxt;
  return 0;
}
/*
-1 2 3 1 0 8 4 6
         5     8

b: 4 6
    s d


1

*/