Cod sursa(job #1802058)

Utilizator calin1Serban Calin calin1 Data 9 noiembrie 2016 20:28:58
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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, int &start)
{
    while(!dq.empty() && vec[i] < vec[dq.back()])
    {
        start = dq.back();

        dq.pop_back();
    }
}

void citire()
{
    int maxim = -inf;

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

    int i_max = 1, j_max = k;

    int tmp = 1;

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

        sterge(i,tmp);

        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,tmp);

        dq.push_back(i);

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

            i_max = tmp;
            j_max = i;
        }
    }

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

    printf("%d ",maxim);
}

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

    citire();

    return 0;
}