Cod sursa(job #2268781)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 25 octombrie 2018 12:07:06
Problema Secventa Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX=((5*(1e5))+5);

int N, K, i, A[NMAX], ans=INT_MIN, Left, Right;

deque <int> D;

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    scanf("%d%d", &N, &K);

    for(i=1; i<=N; i++)
        scanf("%d", &A[i]);

    D.push_back(1);

    for(i=2; i<=N; i++)
    {
        while(!D.empty() && A[D.back()] > A[i])
            D.pop_back();

        D.push_back(i);

        if(D.back()-D.front()>=K)
            D.pop_front();

        if(A[D.front()] > ans)
        {
            ans=A[D.front()];

            Left=i-K+1;
            Right=i;
        }
    }

    printf("%d %d %d\n", Left, Right, ans);

    return 0;
}