Cod sursa(job #1000078)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 21 septembrie 2013 22:24:40
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <climits>
#include <deque>

using namespace std;

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

int N, K;
int A[Nmax], rmq[LgMax][Nmax], lg[Nmax];
char sir[Nmax * 15];
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", &N, &K);

    fgets( sir, Nmax * 15, stdin );

    int i = 0, index = 1;
    int semn = 1;

    while ( sir[i] != '\n' )
    {
        while ( sir[i] == ' ' ) i++;

        if ( sir[i] == '-' )
        {
            semn = -1;
            i++;
        }

        while ( isdigit( sir[i] ) )
        {
            A[index] = A[index] * 10 + ( sir[i] - 48 );
            i++;
        }

        A[index] *= semn;
        semn = 1;
        index++;
    }

    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;
}