Cod sursa(job #2509735)

Utilizator pregoliStana Andrei pregoli Data 14 decembrie 2019 17:55:13
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
#define newline '\n'
#define ll long long
#define uns unsigned
#define deb(x) clog << x << ' '
#define debnewL(x) clog << x << newline
using namespace std;
///************************************
inline void __attribute__ ((constructor)) _cfun();
inline void _cfun()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    ios :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);
}
///************************************

int n, k, x;
deque < pair <int, int> > dq;
int ansmax, l, r;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
    {
        cin >> x;
        while (!dq.empty() && dq.back().first >= x)
            dq.pop_back();
        dq.push_back(make_pair(x, i));
    }

    ansmax = dq.front().first;
    l = 1, r = k;

    for (int i = k + 1; i <= n; i++)
    {
        cin >> x;
        while (!dq.empty() && dq.front().second <= i - k)
            dq.pop_front();

        while (!dq.empty() && dq.back().first >= x)
            dq.pop_back();

        dq.push_back(make_pair(x, i));
        if (dq.front().first > ansmax)
        {
            ansmax = dq.front().first;
            l = i - k + 1;
            r = i;
        }
    }

    cout << l << ' ' << r << ' ' << ansmax;
    return 0;
}