Cod sursa(job #3126979)

Utilizator cattyAninisCatrinel catty Data 7 mai 2023 03:42:53
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>
#define L long long
using namespace std;
ifstream in("secventa.in");
ofstream out("secventa.out");
const int NY=5e5+2;
int n,k,i,j,sh,lg[NY],m,ps,pd;
short r[30][NY];
int main()
{
    in>>n>>k;
    for(i=1;i<=n;++i)
    {
        if(i>1) lg[i]=lg[i/2]+1;
        in>>r[0][i];
    }
    for(i=1;(1<<i)<=n;++i)
        for(j=1;j<=n-(1<<i)+1;++j)
    {
        sh=1<<(i-1);
        r[i][j]=min(r[i-1][j],r[i-1][j+sh]);
    }
    sh=k-(1<<lg[k]);
    n-=k;
    ++n;
    for(i=1;i<=n;++i)
    {
        j=min(r[lg[k]][i],r[lg[k]][i+sh]);
        if(j>m)
            m=j,ps=i,pd=i+k-1;
    }
    out<<ps<<' '<<pd<<' '<<m;
}