Cod sursa(job #2917340)

Utilizator ezluciPirtac Eduard ezluci Data 4 august 2022 14:48:01
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
#ifdef _POSIX_SOURCE
#define getchar getchar_unlocked
#endif // _POSIX_SOURCE
using namespace std;
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];
int lg;


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

   for (int j = 1; j <= lg; ++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)
{
   return min(rmq[a][lg], rmq[b-(1<<lg)+1][lg]);
}


int getint()
{
   char c;
   while ((c = getchar()) && (c == ' ' || c == '\n'));

   int semn = 1, x = 0;
   if (c == '-')
      semn = -1;
   else
      x = c-'0';

   while ((c = getchar()) && isdigit(c))
      x = x*10 + c-'0';

   return semn*x;
}


int main()
{
   freopen("secventa.in", "r", stdin);

   n = getint();
   k = getint();
   for (int i = 1; i <= n; ++i)
      v[i] = getint();

   lg = 31 - __builtin_clz(k);
   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;
}