Cod sursa(job #2328376)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 25 ianuarie 2019 18:00:53
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

deque <int> Q;

const int bsize = (1 << 16);

char ch[bsize+1];

int pos;

int n, k, a[500005], bazamaxima, in, sf;

void read (int &x)
{
    x = 0;
    int semn = 1;

    while (!isdigit(ch[pos]))
    {
        if (ch[pos] == '-') semn = -1;
        pos++;

        if (pos == bsize)
        {
            fread(ch, 1, bsize, stdin);
            pos = 0;
        }
    }

    while (isdigit(ch[pos]))
    {
        x = x * 10 + (ch[pos] - '0');
        pos++;

        if (pos == bsize)
        {
            fread(ch, 1, bsize, stdin);
            pos = 0;
        }
    }

    x *= semn;
}
void citire ()
{
    read(n);
    read(k);

    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
    }
}

void rezolv ()
{
    bazamaxima = -100000;
    for (int i = 1; i <= n; ++i)
    {
        if (!Q.empty() && Q.front() <= i - k) Q.pop_front();

        while (!Q.empty() && a[Q.back()] > a[i])
        {
            Q.pop_back();
        }
        Q.push_back(i);

        if (a[Q.front()] > bazamaxima && i >= k)
        {
            bazamaxima = a[Q.front()];
            in = i - k + 1;
            sf = i;
        }
    }
}

void afis()
{
    cout << in << " " << sf << " " << bazamaxima << '\n';
}

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    ios_base :: sync_with_stdio(false);
    fread(ch, 1, bsize, stdin);
    pos = 0;

    citire();
    rezolv();
    afis();
    return 0;
}