Cod sursa(job #1813775)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 23 noiembrie 2016 11:43:24
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
/// Problema "Secventa" - InfoArena
#include <cstdio>
#include <algorithm>
#include <deque>

#define in "secventa.in"
#define out "secventa.out"
#define NMAX (500000 + 7)
#define inf (- 50000 - 7)
#define DIM (100000 + 7)

using namespace std;
int n, k, v[NMAX], aux, maxn = inf, p, poz;
char buff[DIM];
struct element
{
    int value;
    int key;
} tmp;
deque <element> dq;

inline void goNext()
{
    ++poz;
    if(poz == DIM)
    {
        poz = 0;
        fread(buff, 1, DIM, stdin);
    }
}
void citeste(int &nr)
{
    nr = 0;
    while(buff[poz] < '0' || buff[poz] > '9') goNext();
    while(buff[poz] <= '9' && buff[poz] >= '0')
    {
        nr = nr * 10 + buff[poz] - '0';
        goNext();
    }
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    fread(buff, 1, DIM, stdin);
    //scanf("%d %d", &n, &k);
    citeste(n);
    citeste(k);
    for(int i = 1; i<= k-1; ++i)
    {
        //scanf("%d", &aux);
        citeste(aux);
        tmp.key = i;
        tmp.value = aux;
        while(!dq.empty())
        {
            element ceva = dq.front();
            if(ceva.value >= aux) dq.pop_back();
            else break;
        }
        dq.push_back(tmp);
    }
    for(int i = k; i<= n; ++i)
    {
        //scanf("%d", &aux);
        citeste(aux);
        tmp.key = i;
        tmp.value = aux;
        while(!dq.empty())
        {
            element ceva = dq.front();
            if(ceva.value >= aux) dq.pop_back();
            else break;
        }
        dq.push_back(tmp);
        element hlp = dq.front();
        if(hlp.value > maxn)
        {
            maxn = hlp.value;
            p = i;
        }
        if(hlp.key <= i-k+1) dq.pop_front();
    }
    printf("%d %d %d\n", p-k+1, p, maxn);
    return 0;
}