Cod sursa(job #1000071)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 21 septembrie 2013 22:02:51
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <cstring>

using namespace std;

const int Nmax  = 500005;
const int LgMax = 20;

int N, K;
int rmq[LgMax][Nmax], A[Nmax], lg[Nmax];
int maxim = -INT_MAX, stanga, dreapta;

void RMQ()
{
    for ( int i = 1; i <= N; ++i )
            rmq[0][i] = A[i];

    for ( int i = 1; ( 1 << i ) <= N; ++i )
            for ( int j = 1; j + ( 1 << i ) - 1 <= N; ++j )
            {
                int p = 1 << ( i - 1 );

                rmq[i][j] = min( rmq[i - 1][j], rmq[i - 1][j + p] );
            }

    for ( int i = 2; i <= N; ++i )
            lg[i] = lg[i / 2] + 1;
}

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

    scanf("%d %d", &N, &K);

    for ( int i = 1; i <= N; ++i )
            scanf("%d", &A[i]);

    RMQ();

    int l = 0, r = K - 1;

    while ( r < N )
    {
        l++;
        r++;

        int diff = r - l + 1;
        int k = lg[diff];
        int p = 1 << k;
        int sh = diff - p;

        int m = min( rmq[k][l], rmq[k][l + sh] );

        if ( m > maxim )
        {
            maxim = m;
            stanga = l;
            dreapta = r;
        }
    }

    printf("%d %d %d\n", stanga, dreapta, maxim);

    return 0;
}