Cod sursa(job #742083)

Utilizator visanrVisan Radu visanr Data 28 aprilie 2012 14:40:30
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <cstdio>
#include <cstdlib>
using namespace std;


#define nmax 500010


int v[nmax], deque[nmax], n, k, max = 0, start, end, front, back;


int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int i;
    scanf("%i %i", &n, &k);
    for(i=1; i<=n; ++i) scanf("%i", &v[i]);
    front = 1;
    back = 0;
    for(i=1; i<=n; ++i)
    {
             while(front <= back && v[i] <= v[ deque[back] ]) back--;
             deque[++back] = i;
             if(deque[front] == i-k) front++;
             if(i >= k)
             {
                  if(v[ deque[front] ] > max)
                  {
                        max = v[ deque[front] ];
                        start = i-k+1;
                        end = i;
                  }
             }
    }
    printf("%i %i %i", start, end, max);
    //scanf("%i", &i);
    return 0;
}