Cod sursa(job #2939024)

Utilizator NanuGrancea Alexandru Nanu Data 12 noiembrie 2022 21:30:27
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda cnilc1_2-dq Marime 0.99 kb
#include <fstream>
#include <deque>

using namespace std;

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

#define DIM 500000
#define INF (1LL << 25)

int n, k;
int v[DIM + 1];
deque <int> DQ;

//In Dq retin elementele in ordine crescatoare;

int main() {
  fin >> n >> k;
  for(int i = 1; i <= n; i++)
    fin >> v[i];

  //prelucram primele k elemente;
  for(int i = 1; i <= k; i++) {
    while(!DQ.empty() && v[DQ.back()] > v[i])
      DQ.pop_back();
    DQ.push_back(i);
  }

  int pmax = DQ.front();
  int st = 1, dr = k;
  for(int i = k + 1; i <= n; i++) {
    while(!DQ.empty() && v[DQ.back()] > v[i])
      DQ.pop_back();

    DQ.push_back(i);

    //daca am o secventa mai mare de k elemente elimin elementul din varf;
    if(DQ.front() == i - k)
      DQ.pop_front();
    
    if(v[pmax] < v[DQ.front()]) {
      pmax = DQ.front();
      st = i - k + 1;
      dr = i;
    }
  }

  fout << st << " " << dr << " " << v[pmax];

  return 0;
}