Cod sursa(job #283750)

Utilizator sigridMaria Stanciu sigrid Data 19 martie 2009 18:23:27
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#define dim 500001

int a[dim], c[dim];
int N, K;

int main()
{
    int i, prim, ultim, ok, start, end, max=-32001;

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

    i = 2;
    while(i <= N)
     {


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

      ultim++;
      c[ultim] = i;

      ok = 0;
      while( ( c[ultim] - c[prim] + 1 ) >= K ) 
       {
            prim++;
            ok=1;
       }

      if(ok)
        {
         prim--;

         if( a[c[prim]] >= max )
          {
             max = a[c[prim]];

             start = c[prim];
             end = c[ultim];
          }

        }

      i++;
     }

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

return 0;

}