Cod sursa(job #1801842)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 9 noiembrie 2016 17:36:40
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <deque>
#include <cstdio>

using namespace std;

const int NMax = 5000005;
long long sum=0;
int N,K;
int A[NMax];

deque < int > Dq;

void Read()
{
    scanf("%d%d", &N, &K);

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

void Solve()
{
    Dq.push_back(1);

    int maxi=-30005, ind;

    for(int i=2; i<=N; ++i)
    {
        if(Dq.front()==i-K )
            Dq.pop_front();

        while(!Dq.empty() && A[i]<=A[Dq.back()])
            Dq.pop_back();

        Dq.push_back(i);

        if(i>=K)
        {
            int m=A[Dq.front()];
            if(m>=maxi)
                {maxi=m;
                ind=Dq.front();
                }
        }
    }

    printf("%d %d %d",ind, ind+K-1, maxi);

}

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

    Read();
    Solve();

    return 0;
}