Cod sursa(job #2917336)

Utilizator ezluciPirtac Eduard ezluci Data 4 august 2022 14:38:57
Problema Secventa Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("secventa.in");
ofstream fout ("secventa.out");

const int nMAX = 500e3;
const int lognMAX = 18;

int n, k;
int v[nMAX + 1];
int rmq[nMAX + 1][lognMAX + 1];


void buildRMQ()
{
   for (int i = 1; i <= n; ++i)
      rmq[i][0] = v[i];

   for (int j = 1; (1 << j) <= n; ++j)
      for (int i = 1; i-1 + (1<<j) <= n; ++i)
         rmq[i][j] = min(rmq[i][j-1], rmq[i + (1<<(j-1))][j-1]);
}

int queryRMQ(int a, int b)
{
   int lg = 31 - __builtin_clz(b-a+1);
   return min(rmq[a][lg], rmq[b-(1<<lg)+1][lg]);
}


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

   buildRMQ();

   int max = INT_MIN, dr;
   for (int i = k; i <= n; ++i)
   {
      int qu = queryRMQ(i-k+1, i);

      if (qu > max)
      {
         max = qu;
         dr = i;
      }
   }

   fout << dr-k+1 << ' ' << dr << ' ' << max;
}