Cod sursa(job #1903809)

Utilizator BugirosRobert Bugiros Data 5 martie 2017 12:54:40
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
using namespace std;

ifstream in("secventa.in");
ofstream out("secventa.out");

const int MAXN = 500005;

int n,k;
int v[MAXN];
int prasp,qrasp,bazarasp;
int Deque[MAXN];
int p,q;

void citire()
{
    in >> n >> k;
    for (int i = 1;i <= n;++i)
        in >> v[i];
}

void prelucrare()
{
    p = 1, q = 0;
    for (int i = 1;i <= k;++i)
    {
        while(p <= q && v[Deque[q]] >= v[i])
            --q;
        Deque[++q] = i;
    }
    bazarasp = v[Deque[p]];
    prasp = 1;
    qrasp = k;
    for (int i = 2;i <= n - k + 1;++i)
    {
        if (Deque[p] <= i - 1)
            ++p;
        while(p <= q && v[Deque[q]] >= v[i + k - 1])
            --q;
        Deque[++q] = i + k - 1;
        if (v[Deque[p]] > bazarasp)
        {
            bazarasp = v[Deque[p]];
            prasp = i;
            qrasp = i + k - 1;
        }
    }
}

int main()
{
    citire();
    prelucrare();
    out << prasp << ' ' << qrasp << ' ' << bazarasp << '\n';
    return 0;
}