Cod sursa(job #1802041)

Utilizator calin1Serban Calin calin1 Data 9 noiembrie 2016 20:11:39
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 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 = 1,j_max = k;

    bool ok = false;

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

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

        sterge(i);

        dq.push_back(i);

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

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

        if(i - dq.front() + 1 > k)
        {
            if(ok)
            {
                i_max = dq.front();

                j_max = dq.front() + k - 1;

                ok = false;
            }

            dq.pop_front();
        }

        sterge(i);

        dq.push_back(i);

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

            ok = true;
        }
    }

    if(ok)
    {
        i_max = n - k + 1;

        j_max = n;
    }

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

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

    citire();

    return 0;
}