Cod sursa(job #2911412)

Utilizator ArseniuVictorStefanArseniu Victor Stefan ArseniuVictorStefan Data 29 iunie 2022 12:10:53
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <vector>
#include <set>
#include <deque>

using namespace std;

//ifstream cin("secventa.in");
//ofstream cout("secventa.out");

int n, k, a[500000], deq[500010], front, top;

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];

    front = 0, top = -1;
    for(int i = 0; i < k; i++)
    {
        while(top >= front && a[deq[top]] >= a[i])
            top--;
        deq[++top] = i;
    }

    int maxi = deq[front], r = k - 1;
    for(int i = k; i < n; i++)
    {
        while(top >= front && deq[front] <= i - k)
            front++;
        while(top >= front && a[deq[top]] >= a[i])
            top--;
        deq[++top] = i;

        if(a[maxi] < a[deq[front]])
        {
            maxi = deq[front];
            r = i;
        }
    }

    cout << r - k + 2 << ' ' << r + 1 << ' ' << a[maxi] << '\n';
    return 0;
}