Cod sursa(job #2835012)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 17 ianuarie 2022 23:07:16
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <deque>

const int MAX_N  = 5 * 1e5;
int a[1 + MAX_N];
std::deque<int> dq;

int main() {
  std::ifstream fin("secventa.in");
  std::ofstream fout("secventa.out");
  int n, k;
  fin >> n >> k;
  for (int i = 1; i <= n; i++) {
    fin >> a[i];
  }
  int mx = 0, st, dr;
  for (int i = 1; i <= n; i++) {
    if (!dq.empty() && dq.front() == i - k) {
      dq.pop_front();
    }
    while (!dq.empty() && a[i] <= a[dq.back()]) {
      dq.pop_back();
    }
    dq.push_back(i);
    if (a[dq.front()] > mx) {
      mx = a[dq.front()];
      st = i - k + 1;
      dr = i;
    }
  }
  fout << st << " " << dr << " " << mx;
  return 0;
}