Cod sursa(job #2536487)

Utilizator SochuDarabaneanu Liviu Eugen Sochu Data 2 februarie 2020 09:42:36
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("03")
#define N 500005

using namespace std;

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

int n , k;
short a[N];
deque < int > d;

int main()
{
    ios_base::sync_with_stdio(false) , f.tie(0) , g.tie(0);

    int inc = 0 , sf = 0 , i;
    short baza = -30003;

    f >> n >> k;

    for(i = 1 ; i <= n ; ++i)
        f >> a[i];

    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;
}