Cod sursa(job #297997)

Utilizator sigridMaria Stanciu sigrid Data 5 aprilie 2009 19:16:37
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>

#define dim 500001
#define inf -32001

int a[dim], c[dim];

int N, K;

int main()
{
    
 int i, prim, ultim, start, end, max;

 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]=1;

 i=2;
 max = inf;

 while( i <= N )
  {

   if(i == ( c[prim] + K ) )
     ++prim;

   while( ( a[i] < a[c[ultim]] ) && ( prim <= ultim ) )
     --ultim;

   ++ultim;
   c[ultim] = i;

   if( i >= K )
    if( a[c[prim]] > max )
    {
        max = a[c[prim]];
        
        start = c[ultim] - K + 1;
        end = c[ultim];
    }

   ++i;
}

printf("%d %d %d \n", start, end, max);

return 0;
}