Cod sursa(job #290257)

Utilizator cristikIvan Cristian cristik Data 27 martie 2009 18:16:01
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <stdio.h>
#define max 500001
int a[max],deque[max],n,k,front,back,i,j,min=-300100,begin,end;
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]);
    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(min<a[deque[front]]) min=a[deque[front]],begin=i-k+1,end=i;
    }
    printf("%d %d %d",begin,end,min);
    return 0;
}