Cod sursa(job #1398630)

Utilizator borcanirobertBorcani Robert borcanirobert Data 24 martie 2015 12:31:13
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <deque>
using namespace std;

FILE *f = fopen( "secventa.in", "r" );
FILE *g = fopen( "secventa.out", "w" );

const int MAX = 500010;
int a[MAX];
int N, K;
deque<int> Q;
int maxim;
int poz;

int main()
{
    int i, j;

    fscanf( f, "%d%d", &N, &K );
    for ( i = 1; i <= N; i++ )
        fscanf( f, "%d", &a[i] );

    Q.push_back( 1 );
    for ( i = 2; i <= K; i++ )
    {
        while ( a[Q.back()] > a[i] )
        {
            Q.pop_back();
            if ( Q.empty() ) break;
        }
        Q.push_back( i );
    }

    maxim = a[Q.front()];
    for ( i = K + 1; i <= N; i++ )
    {
        while ( Q.front() < i - K + 1 )
            Q.pop_front();

        while ( a[Q.back()] > a[i] )
        {
            Q.pop_back();
            if ( Q.empty() ) break;
        }
        Q.push_back( i );

        if ( a[Q.front()] > maxim )
        {
            maxim = a[Q.front()];
            poz = i - K + 1;
        }
    }

    fprintf( g, "%d %d %d\n", poz, poz + K - 1, maxim );

    fclose(f);
    fclose(g);
    return 0;
}