Cod sursa(job #1775226)

Utilizator borcanirobertBorcani Robert borcanirobert Data 10 octombrie 2016 08:43:19
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <cstdio>
#include <deque>
using namespace std;

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

const int MAX = 500005;
const int MAXR = 100000;
const int INF = 0x3f3f3f3f;
int N, K;
int a[MAX];
char r[MAXR];
int p = MAXR - 1;
deque<int> Q;
int pi, pf, minim = -INF;

void Read();
void Solve();
void Get( int& x );
void Next();

int main()
{
    Read();
    Solve();

    fprintf(g, "%d %d %d\n", pi, pf, minim);

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

void Read()
{
    int i, x;
    Get(N); Get(K);

    for ( i = 1; i <= N; i++ )
    {
        Get(x); a[i] = x;
    }
}

void Solve()
{
    int i, p = 1;

    for ( i = 1; i < K; i++ )
    {
        while ( !Q.empty() && a[i] < a[Q.back()] )
            Q.pop_back();
        Q.push_back(i);
    }

    p = 1;
    for ( i = K; i <= N; i++ )
    {
        while ( !Q.empty() && a[i] < a[Q.back()] )
            Q.pop_back();
        Q.push_back(i);

        while ( i - Q.front() + 1 > K )
        {
            p = Q.front() + 1;
            Q.pop_front();
        }

        if ( a[Q.front()] > minim )
        {
            minim = a[Q.front()];
            pi = p, pf = i;
        }
        else
            if ( a[Q.front()] == minim && p < pi )
            {
                pi = p, pf = i;
            }
    }
}

void Get( int& x )
{
    char c;
    for ( ; r[p] < '0' || r[p] > '9'; c = r[p], Next() );

    for ( x = 0; r[p] >= '0' && r[p] <= '9'; Next() )
        x = ( x * 10 ) + ( r[p] - '0' );

    if ( c == '-' )
        x = -x;
}

void Next()
{
    if ( ++p == MAXR )
    {
        fread( r, 1, MAXR, f );
        p = 0;
    }
}