Cod sursa(job #2929311)

Utilizator raresgherasaRares Gherasa raresgherasa Data 25 octombrie 2022 15:52:14
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NM = 5e5 + 5;

int a[NM], n, k, mx, w, r;
deque<int>dq;

int main(){
  fin >> n >> k;
  for (int i = 1; i <= k; i++){
    fin >> a[i];
    while (!dq.empty() && a[i] <= a[dq.back()]){
      dq.pop_back();
    }
    dq.push_back(i);
  }
  mx = a[dq.front()];
  w = k;
  for (int i = k + 1; i <= n; i++){
    fin >> a[i];
    if (i - dq.front() + 1 > 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()];
      w = i;
    }
  }
  fout << w - k + 1 << " " << w << " " << mx;
}