Cod sursa(job #297938)

Utilizator sigridMaria Stanciu sigrid Data 5 aprilie 2009 18:38:19
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<stdio.h>

#define dim 500001
#define inf -32001

int N, K;

int a[dim], c[dim];

int main()
{
    int i, prim, ultim, max, start, end;
    
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    
    scanf("%d %d", &N, &K);
    
    for(i = 1; i <= N; i++)
          scanf("%d", &a[i]);
          
    prim = ultim = 1 ;
    c[prim] = a[1];
    
    i = 2;
    
    max = inf;

    N++;
    
    while(i <= N)
    {
            //actualizez maximul
            
            if( ( c[ultim] - c[prim] + 1 ) >= K )
                {
                           if( a[c[prim]] > max )
                           {
                               max = a[c[prim]];
                    
                               start = c[prim];
                               end = c[ultim];
                    
                    //prim++;
                            }
                             
                            prim++;
                } 
                 //else if( a[c[prim]] == max )
                          //end = a[c[ultim]];
            
            //adaug elementul i
            
            while( ( prim <= ultim ) && ( a[i] < a[c[ultim]] ) )
                   ultim--;
                   
            ultim++;
            c[ultim] = i;
            
            i++;
    }
    
    printf("%d %d %d \n", start, end, max);
    
    return 0;
}