Cod sursa(job #1511410)

Utilizator juniorOvidiu Rosca junior Data 26 octombrie 2015 18:42:57
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <queue>
#include <fstream>

using namespace std;

int bmax, i, k, minv, d, a[500001], n, c1, c2, s, l[500001];
ifstream f ("secventa.in");
ofstream g ("secventa.out");
deque<int> dq;

int main() {
  f >> n >> k;
  for (i = 1; i <= n; i++)
    f >> a[i];
  bmax = -30001; dq.push_back(a[1]); l[s] = 1;
  for (i = 2; i <= n; i++) {
    while (a[i] <= dq.back() and not dq.empty()) // !! s <= d
      dq.pop_back();
    dq.push_back(a[i]); l[a[i]] = i;
    if (i - l[dq.front()] == k)
      dq.pop_front();
    if (k <= i)
      if (dq.front() > bmax) {
        c1 = i - k + 1; c2 = i; bmax = dq.front();
      }
  }
  g << c1 << " " << c2 << " " << bmax;
  return 0;
}
/*
-1 2 3 1 0 8 4 6
         5     8

b: 4 6
    s d


1

*/