Cod sursa(job #2883094)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 1 aprilie 2022 10:20:20
Problema Secventa Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

short v[N];

int main() {
  ifstream cin("secventa.in");
  ofstream cout("secventa.out");
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  int n, k, ans = -1e9, l, r;
  cin >> n >> k;
  deque<short> dq;
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
    while (!dq.empty() && dq.front() < i - k + 1)
      dq.pop_front();
    while (!dq.empty() && v[i] <= v[dq.back()])
      dq.pop_back();
    dq.push_back(i);
    if (i >= k - 1 && v[dq.front()] > ans) {
      ans = v[dq.front()];
      l = i - k + 1;
      r = i;
    }
  }
  cin.close();
  cout << l + 1 << " " << r + 1 << " " << ans << "\n";
  cout.close();
  return 0;
}