Cod sursa(job #1000068)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 21 septembrie 2013 21:55:55
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 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()
{
    ifstream f("secventa.in");
    ofstream g("secventa.out");

    f >> N >> K;

    string file( ( istreambuf_iterator <char>(f) ), istreambuf_iterator<char>() );

    int nr = 0;
    int semn = 1;
    int index = 1;

    int ll = file.length();

    for ( int i = 1; i < ll; ++i )
    {
        if ( file[i] == '-' )
                semn = -1;
        else
            if ( isdigit( file[i] ) )
                    nr = nr * 10 + ( file[i] - 48 );
            else
            {
                nr *= semn;
                A[ index++ ] = nr;

                nr = 0;
                semn = 1;
            }
    }

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

    g << stanga << " " << dreapta << " " << maxim << "\n";

    return 0;
}