Cod sursa(job #2412741)

Utilizator LuscanAlexLuscan Alexandru LuscanAlex Data 22 aprilie 2019 15:19:10
Problema Secventa Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <deque>
using namespace std;

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

void Get(int &x);

deque <int> d;

int a[500005], n, k, pi, ps, ma, pz;

int main()
{
    int i;
    Get(n), Get(k);

    for (i = 1; i <= k; ++i)
    {
        Get(a[i]);

        while (!d.empty() && a[d.front()] > a[i])
            d.pop_front();
        d.push_front(i);
    }

    ma = d.back();
    pz = k;
    for (i = k + 1; i <= n; ++i)
    {
        if (i - d.back() >= k)
            d.pop_back();

        Get(a[i]);

        while (!d.empty() && a[d.front()] > a[i])
            d.pop_front();
        d.push_front(i);

        if (a[d.back()] > a[ma] || (a[d.back()] == a[ma] && i < pz))
        {
            ma = d.back();
            pz = i;
        }
    }

    fout << pz - k + 1 << ' ' << pz << ' ' << a[ma];
}

const int lim = 100000;
int p = lim - 1;
char s[lim];

void Next()
{
    if (++p == lim)
        fin.get(s, lim + 1, EOF), p = 0;
}

void Get(int &x)
{
    int sgn = 1;

    for (; s[p] < '0' || s[p] > '9'; Next())
        if (s[p] == '-')
            sgn = -1;

    for (x = 0; s[p] >= '0' && s[p] <= '9'; Next())
        x = x * 10 + s[p] - '0';

    x *= sgn;
}