Cod sursa(job #812245)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 13 noiembrie 2012 18:08:07
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
#include <cstdlib>

int v[500001],deque[500001];
int min,max,baza,n,k;


int main ()
{
    FILE *f,*g;
    f = fopen("secventa.in","r");
    g = fopen("secventa.out","w");
    
    fscanf(f,"%d %d",&n,&k);
    for ( int i = 1; i <= n ; i++ )
        fscanf(f,"%d",&v[i]);
    
    min = 1;
    max = 0;
    baza = v[1];
    
    for ( int i = 1; i <= n ; i++ )
    {
        while ( v[i] < v[deque[max]] && max >= min ) max--;
        
        deque[++max] = i;
        
        if ( deque[min]  == i-k )    min++;
        
        if ( i >= k && baza < v[deque[min]] )  
        {
             baza = v[deque[min]];
             min = i-k+1;
             max = i;
        }
        
    }
    
    fprintf(g,"%d %d %d",deque[min],deque[max],baza);
    
    fclose(f);
    fclose(g);
    
    return 0;
}