Cod sursa(job #3140010)

Utilizator RolandPetreanPetrean Roland RolandPetrean Data 3 iulie 2023 14:31:41
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
// https://infoarena.ro/problema/secventa
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int main() {
  int n, k;
  fin>>n>>k;

  vector<int> a(n);
  for (int i=0; i<n; ++i) fin>>a[i];

  deque<int> mini{};
  for (int i=0; i<k; ++i) {
    while (!mini.empty() && a[mini.back()] >= a[i]) mini.pop_back();
    mini.push_back(i);
  }

  int maxmin=a[mini.front()], dr=k-1;
  for (int i=k; i<n; ++i) {
    while (!mini.empty() && mini.front() <= i-k) mini.pop_front();
    while (!mini.empty() && a[mini.back()] >= a[i]) mini.pop_back();
    mini.push_back(i);

    if (a[mini.front()] > maxmin) {
      maxmin = a[mini.front()];
      dr = i;
    }
  }

  fout<<dr-k+2<<" "<<dr+1<<" "<<maxmin;
}