Cod sursa(job #3127184)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 7 mai 2023 13:15:49
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, A[500005], k, P1, P2;
deque< pair<int, int> > D;

int main()
{
    f >> n >> k;
    for(int i = 1; i <= n; i ++)
        f >> A[i];

    D.push_back({A[1], 1});

    for(int i = 2; i <= k; i ++)
    {
        while(!D.empty() && A[i] < D.back().first)
            D.pop_back();
        D.push_back({A[i], i});
    }

    int maxi = D.front().first;
    int pozi = 2, pozf = k + 1;
    P1 = 1; P2 = k;
    while(pozi <= n - k + 1)
    {
        while(!D.empty() && D.front().second < pozi)D.pop_front();
        while(!D.empty() && D.back().first > A[pozf])D.pop_back();

        D.push_back({A[pozf], pozf});
        if(maxi < D.front().first)
        {
            maxi = D.front().first;
            P1 = pozi; P2 = pozf;
        }
        pozi ++; pozf ++;
    }

    g << P1 << " " << P2 << " " << maxi;
    return 0;
}