Cod sursa(job #296117)

Utilizator klamathixMihai Calancea klamathix Data 4 aprilie 2009 11:51:38
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<stdio.h>

#define MAXN 501000
#define INITMAX -320000
#define PARSM MAXN*7

using namespace std;

int A[MAXN], deque[MAXN],sign, i , j , N , back , front, k, left, right, minb = INITMAX;
char s[PARSM];

void parsare()
{
     int i , j, sign ;
     
     fgets(s,PARSM,stdin);
      
      for( i = 1 , j = 0 ; i <= N ; i++)
      {
           while( s[j] == ' ' )  j++;
           
           if(s[j] == '-') { sign = 1; j ++;}
            else sign = 0;
           
           while(s[j] >= '0' && s[j] <= '9') A[i] = A[i]*10 + s[j++] - 48;
       
           if( sign ) A[i] *= -1;
           
       }
}
            
     
     
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    
    scanf("%d %d\n",&N ,&k);
    
    parsare();
    
   
    front = 1; back = 0;
    
    for( i = 1; i <= N ; i++)
    {
         while( front <= back && A[i] <= A[deque[back]])
         back --;
         
         deque[++back] = i;
         
         if( deque[front] == i - k) front++;
         
         if( i >= k ) 
         {
             if(deque[front] > minb)
             {
                            minb = A[deque[front]]; 
                            left = i - k + 1;
                            right = i;
             }
         }
    }           
   
    printf( "%d %d %d", left, right, minb);
    
    return 0;
}