Cod sursa(job #985250)

Utilizator gbi250Gabriela Moldovan gbi250 Data 17 august 2013 02:12:38
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>
#include <deque>
#include <climits>
#define SIZE 500002
using namespace std;

int i, n, k, pz, pos_elem, MAX=INT_MIN, v[SIZE];
deque <int> dq;

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", &v[i]);
    for(i=1;i<=n;++i)
    {
        while(!dq.empty() && v[dq.back()]>=v[i])
            dq.pop_back();
        while(!dq.empty() && i-k>=dq.front())
            dq.pop_front();
        dq.push_back(i);
        if(i>=k && v[dq.front()]>MAX)
        {
            MAX=v[dq.front()];
            pz=i-k+1;
        }
    }
    printf("%d %d %d", pz, pz+k-1, MAX);
    return 0;
}