Cod sursa(job #1714453)

Utilizator silkMarin Dragos silk Data 8 iunie 2016 12:26:41
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#define NMax 500005
#define INF 30005
#define DIM 10000
char buff[DIM];
int poz=0;

int v[NMax];
int deque[NMax];

void citeste(int &numar)
{
     numar = 0;
     while (buff[poz] < '0' || buff[poz] > '9')
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
}

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

    int sf,inc,i,n,k,ans=-INF,start,stop;
    scanf("%d %d",&n,&k);

    for( i = 1; i <= n; ++i ) citeste( v[i] );

    sf = -1;
    inc = 0;
    for( i = 1; i <= k; ++i )
    {
            while( sf - inc + 1 > 0 && v[i] <= v[ deque[sf] ] ) sf--;
            deque[++sf] = i;
    }

    for( i = k + 1; i <= n; ++i )
    {
        if( ans < v[ deque[inc] ] ) { start = i - k; stop = i - 1; ans = v[ deque[inc] ]; }

        while( sf - inc + 1 > 0 && deque[inc] <= i - k ) inc++;

        while( sf - inc + 1 > 0 && v[i] <= v[ deque[sf] ] ) sf--;
        deque[++sf] = i;

    }

        if( ans < v[ deque[inc] ] ) { start = n - k + 1; stop = n; ans = v[ deque[inc] ]; }

    printf("%d %d %d\n",start,stop,ans);



return 0;
}