Cod sursa(job #1802009)

Utilizator calin1Serban Calin calin1 Data 9 noiembrie 2016 19:53:10
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <iostream>
#include <cstdio>
#include <deque>
#include <climits>
#define N 500005
#define inf INT_MAX

using namespace std;

int n, k, vec[N];

deque <int> dq;

void sterge(int i)
{
    while(!dq.empty() && vec[i] < vec[dq.back()])
    {
        dq.pop_back();
    }
}

void citire()
{
    int maxim = -inf;
    int i_max,j_max;

    scanf("%d %d\n",&n,&k);

    for(int i = 1 ; i <= k - 1 ; ++i)
    {
        scanf("%d ",&vec[i]);

        sterge(i);

        dq.push_back(i);
    }

    for(int i = k ; i <= n ; ++i)
    {
        scanf("%d ",&vec[i]);

        if(i - dq.front() + 1 > k)
        {
            dq.pop_front();
        }

        sterge(i);

        dq.push_back(i);

        if(vec[dq.front()] > maxim)
        {
            maxim = vec[dq.front()];

            i_max = dq.front();
            j_max = i;
        }
    }

    printf("%d %d %d",i_max,j_max,maxim);
}

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

    citire();

    return 0;
}