Cod sursa(job #2426519)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 28 mai 2019 15:03:21
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>
#define NMAX 500005

using namespace std;

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

int n , k;
short x;
vector < short > a;
deque < int > d;

int main()
{
    int inc = 0 , sf = 0 , baza = -NMAX , i;
    a.push_back(0);

    f >> n >> k;

    for(i=1;i<=n;i++)
    {
        f >> x;
        a.push_back(x);
    }

    d.push_front(1);

    for(i=1;i<=n;i++)
    {
        while(!d.empty() && a[i] <= a[d.back()])
            d.pop_back();

        d.push_back(i);

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

        if(i >= k)
        {
            if(a[d.front()] > baza)
            {
                baza = a[d.front()];

                inc = i - k + 1;

                sf = i;
            }
        }
    }

    g << inc << ' ' << sf << ' ' << baza;

    return 0;
}