Cod sursa(job #2911416)

Utilizator ArseniuVictorStefanArseniu Victor Stefan ArseniuVictorStefan Data 29 iunie 2022 12:19:33
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>

using namespace std;

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    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 && a[deq[top]] >= a[i])
            top--;
        deq[++top] = i;
        while(top >= front && deq[front] <= i - k)
            front++;

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

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