Cod sursa(job #1000076)

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

using namespace std;

const int Nmax  = 500005;

int N, K;
int A[Nmax];
char sir[Nmax * 15];
int maxim = -INT_MAX, stanga, dreapta;

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

    deque <int> DQ;

    for ( int i = 1; i <= N; ++i )
    {
        while ( DQ.size() && DQ.front() < i - K + 1 )
                DQ.pop_front();

        while ( DQ.size() && A[ DQ.back() ] >= A[i] )
                    DQ.pop_back();

        DQ.push_back( i );

        int m = A[ DQ.front() ];

        if ( m > maxim && i >= K )
        {
            maxim = m;
            stanga = i - K +  1;
            dreapta = i;
        }
    }

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

    return 0;
}