Cod sursa(job #812311)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 13 noiembrie 2012 19:26:19
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <cstdlib>

int v[500001],deque[500001];
int min,max,baza = -30001,n,k;
int b;

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;
    b = 0;
    
    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]];
             b = i;
            
        }
        
    }
    
    fprintf(g,"%d %d %d",b-k+1,b,baza);
    
    fclose(f);
    fclose(g);
    
    return 0;
}