Cod sursa(job #296075)

Utilizator klamathixMihai Calancea klamathix Data 4 aprilie 2009 10:12:15
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>

#define MAXN 500010
#define INITMAX -32000

using namespace std;

int A[MAXN], deque[MAXN], i , j , N , back , front, k, left, right, mins, maxs = INITMAX;

int main()
{
    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]);
         
    
    back = 0; front = 1;
    
    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 ) mins = A[deque[front]];
         
         if( mins > maxs) {
                         maxs = mins;
                         left = deque[front];
                         right = left + k - 1;
                         }
    }
    
    printf("%d %d %d",left,right,maxs);
    
    return 0;
}