Cod sursa(job #186433)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 27 aprilie 2008 22:27:53
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
# include <stdio.h>

# define inf 500001
# define FIN "secventa.in"
# define FOUT "secventa.out"

long v[500001];
long deque[500001];

int main()
{
    long n,k,i;
    
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    
    scanf("%ld %ld", &n, &k);
    for (i = 1; i <= n; i++)
      scanf("%ld", &v[i]);
      
    long start=1, stop=0;
    v[0]=-inf;
    
    for (i = 1; i <= k; i++)
      {
           while (v[deque[stop]]>v[i]) stop--;
           deque[++stop]=i;
      }
    
    long min=v[deque[start]], poz=k;
    
    for (i = k+1; i <= n; i++)
      {
           while (deque[start]<i-k+1) start++;
           while (v[deque[stop]]>v[i])
              if (stop!=start-1) stop--;
                            else break;
           deque[++stop]=i;
           if (v[deque[start]]>min)
             {
                 min=v[deque[start]];
                 poz=i;
             }
      }
    
    printf("%ld %ld %ld",poz-k+1,poz,min);
    
    return 0;
}