Cod sursa(job #2954761)

Utilizator ezluciPirtac Eduard ezluci Data 15 decembrie 2022 11:41:10
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const string FILE_NAME = "secventa";
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 500e3;

int n, k;
int v[nMAX + 2];
deque<int> dq;

int main()
{
   fin >> n >> k;
   for (int i = 1; i <= n; ++i)
      fin >> v[i];
   
   for (int i = 1; i <= k; ++i)
   {
      if (dq.empty())
         dq.push_back(i);
      else
      {
         while (!dq.empty() && v[dq.back()] >= v[i])
            dq.pop_back();
         dq.push_back(i);
      }
   }
   
   int st, dr, maxim = INT_MIN;

   for (int i = k+1; i <= n+1; ++i)
   {
      if (v[dq.front()] > maxim)
      {
         maxim = v[dq.front()];
         st = i-k;
         dr = i-1;
      }

      if (dq.empty())
         dq.push_back(i);
      else
      {
         while (!dq.empty() && v[dq.back()] >= v[i])
            dq.pop_back();
         dq.push_back(i);
      }

      if (dq.front() == i-k)
         dq.pop_front();
   }

   fout << st << ' ' << dr << ' ' << maxim;
}