Cod sursa(job #1803429)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 11 noiembrie 2016 13:55:26
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>

int n,k;
int maxim=-(1<<30);
int a[5000001],sfarsit;


int inc,sf;
long long int arr[5000001];

char b[4096];
int s;

bool isdigit(char c)
{
    return c>='0' && c<='9';
}

char citire_caracter()
{
    s++;
    if (s == 4096)
    {
        s = 0;
        fread(b, 1, 4096, stdin);
    }
    return b[s];
}

int citire_int()
{
    char c;
    int n=0;
    while (!isdigit(c = citire_caracter()) && c != '-');
    int semn = 1;
    if (c == '-')
    {
        n = 0;
        semn = -1;
    }
    else
    {
        n = c - '0';
    }
    while (isdigit(c = citire_caracter()))
    {
        n = 10 * n + c - '0';
    }
    return n *= semn;
}

void solve()
{
    n=citire_int();
    k=citire_int();
    a[1]=citire_int();

    arr[sf++]=1;

    for(int i=2; i<k; i++)
    {
        a[i]=citire_int();
        while(sf-inc!=0 && a[arr[sf-1]]>a[i])
            sf--;
        arr[sf++]=i;
    }

    for(int i=k; i<=n; i++)
    {
        a[i]=citire_int();
        if(sf-inc!=0 && arr[inc]<=i-k)
            inc++;
        while(sf-inc!=0 && a[arr[sf-1]]>a[i])
            sf--;
        arr[sf++]=i;

        if(a[arr[inc]]>maxim && i>=k-1)
        {
            maxim=a[arr[inc]];
            sfarsit=i;
        }
    }

    printf("%d %d %d\n",sfarsit-k+1,sfarsit,maxim);
}

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