Cod sursa(job #2033882)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 7 octombrie 2017 11:31:40
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <iostream>
#include <cstdio>
#include <deque>
#define NMAX 500005
#define DIM 1000000

using namespace std;

int n, k, v[NMAX], poz, maxim = -30005, curs;
char buff[DIM];
deque <int> dq;

void adv()
{
    curs++;
    if(curs >= DIM)
    {
        fread(buff, 1, DIM, stdin);
        curs = 0;
    }
}

int getInt()
{
    int nr = 0, semn = 1;
    while(!(buff[curs] >= '0' && buff[curs] <= '9'))
    {
        if(buff[curs] == '-')
        {
            semn = -1;
        }
        adv();
    }

    while(buff[curs] >= '0' && buff[curs] <= '9')
    {
        nr = nr*10 + buff[curs] - '0';
        adv();
    }
    return semn * nr;
}

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

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)
            dq.pop_front();
        if(i>=k)
            if(v[dq.front()] > maxim)
            {
                poz = i;
                maxim = v[dq.front()];
            }
    }
    printf("%d %d %d", poz-k+1, poz, maxim);
}

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