Cod sursa(job #1607513)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 21 februarie 2016 12:17:49
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#include <string.h>


int sir[500001];
int coada[500001];
char buff[1LL<<25];
int asd,offset;
int nm;

int n,i,k,sc,ec;
int bzcm=-320000, end, st;

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);

    scanf("%d %d\n", &n, &k);

    scanf("%d ", &sir[1]);
    coada[1] = 1;
    sc = 1;
    ec = 1;
    gets( buff );

    nm = strlen(buff);
    for ( i = 2; i <= n; ++i )
    {
        asd = 1;
        if ( buff[ offset ] == '-' )
        {
            asd = -1;
            offset++;
        }
        for (; buff[ offset ]!=' ' && offset < nm; offset++ )
        {
            sir[i]*=10;
            sir[i]+=buff[ offset ] - '0';
        }
        offset++;

        sir[i] *= asd;

        if ( (i-1)- coada[sc] + 1 == k )
            ++sc;
        while ( sir[ coada[ec] ] > sir[i] && ec >= sc)
            --ec;
        ++ec;
        coada[ec] = i;
        if ( i > (k-1) )
        if ( sir[ coada[sc] ] > bzcm )
        {
            bzcm = sir[ coada[sc] ];
            st = i-k+1;
            end = i;
        }
    }

    printf("%d %d %d\n", st,end,bzcm);

    return 0;
}