Cod sursa(job #1000074)

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

using namespace std;

const int Nmax  = 500005;

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

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]);

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