Cod sursa(job #247471)

Utilizator nparfene2004Parfene Narcis nparfene2004 Data 23 ianuarie 2009 07:29:10
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
 #include<stdio.h>  
 #define Dim 500001  
   
 int q[Dim], x, max ;  
 long ind[Dim] ;  
 long poz, pr, ul, n, k, i, p ;  
   
 int main()  
 {  
  freopen("secventa.in","r",stdin) ;  
  freopen("secventa.out","w",stdout) ;  
   
  scanf("%ld %ld",&n,&k) ;  
   
  // calculez minimul din primele k:  
  pr = 0 ; ul = -1 ;  
  for (i=1; i<=k; i++)  
  {  
   scanf("%d",&x) ;  
    while ((pr<=ul)&&(q[ul] >= x)) ul-- ;  
    q[++ul] = x ;  
    ind[ul] = i ;  
   }  
  max = q[pr] ;  
  poz = 1 ;  
  p = 1;  
  // calculez restul:  
  for ( ; i<=n; i++)  
   {  
   scanf("%d",&x) ;  
    while ((q[ul] >= x) && (pr<=ul)) ul-- ;  
    q[++ul] = x ;  
    ind[ul] = i ;  
    p++ ;  
    if (ind[pr] <= i-k) pr++ ;  
    if (max < q[pr]) { max = q[pr] ;poz = p; }  
   }  
   
  printf("%ld %ld %d\n",poz,poz+k-1,max) ;  
  return 0 ;  
 }