Cod sursa(job #1608786)

Utilizator BugirosRobert Bugiros Data 22 februarie 2016 12:54:35
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
using namespace std;

const int MAXN = 500005;

int v[MAXN];

int prasp,qrasp,bazarasp = -1;

int deque[MAXN];
int p = 1,q = 0;

int n,k;

void adaugare(int poz)
{
    while(p <= q && v[deque[q]] >= v[poz])
        deque[q--] = 0;
    deque[++q] = poz;
}

void eliminare(int poz)
{
    if (deque[p] == poz)
        deque[p++] = 0;
}

void citire()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    for (int i = 1;i <= n;++i)
        scanf("%d",&v[i]);
}

void prelucrare()
{
    for (int i = 1;i <= k;++i)
        adaugare(i);
    bazarasp = v[deque[p]];
    prasp = 1;
    qrasp = k;
    for (int i = 2;i <= n - k + 1;++i)
    {
        eliminare(i - 1);
        adaugare(i + k - 1);
        if (v[deque[p]] > bazarasp)
        {
            bazarasp = v[deque[p]];
            prasp = i;
            qrasp = i + k - 1;
        }
    }
}


int main()
{
    citire();
    prelucrare();
    printf("%d %d %d\n",prasp,qrasp,bazarasp);
    return 0;
}