Cod sursa(job #2033812)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 7 octombrie 2017 10:54:51
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 500005

using namespace std;

int n, k, v[NMAX], poz, maxim;
deque <int> dq;

void read()
{
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; ++i)
        scanf("%d", &v[i]);
}

void solve()
{
    for(int i=1; i<=n; ++i)
    {
        while(!dq.empty() && v[dq.back()] >= v[i])
            dq.pop_back();
        dq.push_back(i);
        if(dq.front() < i-k+1)
            dq.pop_front();
        if(i>k)
            if(v[dq.front()] > v[maxim])
            {
                poz = i;
                maxim = dq.front();
            }
    }
    printf("%d %d %d", poz-k+1, poz, v[maxim]);
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    read();
    solve();
    return 0;
}