Cod sursa(job #812277)

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

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


int main ()
{
    int a,b;
    
    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;
    
    
    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]];
             a = i-k+1;
             b = i;
            
    
        }
        
    }
    
    printf("%d %d %d",a,b,baza);
    
    fclose(f);
    fclose(g);
    //system("pause");
    return 0;
}