Cod sursa(job #2392089)

Utilizator oogaboogauvuvwevwevwe onyetenyevwe ugwemubwem ossas oogabooga Data 29 martie 2019 17:29:07
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <deque>
#include <limits.h>

using namespace std;

const int MX = 5000000;

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

deque <int> d;
int n;
int k;
int v[MX + 5];
int m[MX + 5];
int l;
int r;
int vl = INT_MIN;

int main()
{
    in>>n>>k;

    for(int i = 1; i <= n; ++i)
    {
        in>>v[i];
    }

    for(int i = 1; i <= n; ++i)
    {
        while(!d.empty() and v[i] < v[d.back()])
        {
            d.pop_back();
        }

        d.push_back(i);

        if(d.front() == i - k)
        {
            d.pop_front();
        }

        if(i >= k)
        {
            m[i] = v[d.front()];
        }
    }

    while(!d.empty())
    {
        d.pop_back();
    }

    for(int i = 1, j = n; i <= k; ++i, --j)
    {
        m[i] = m[k];
        m[j] = m[n];
    }

    m[n + 1] = INT_MIN;

    int st = 1;
    int sf = 1;

    for(int i = 1; i <= n; ++i)
    {
        if(m[i] != m[i + 1])
        {
            int lg = sf - st + 1;

            if(lg >= 3 && m[st] > vl)
            {
                vl = m[st];
                l = st;
                r = sf;
            }

            st = sf = i + 1;
        }
        else
        {
            ++sf;
        }
    }

    out<<l<<" "<<r<<" "<<vl;

    return 0;
}