Cod sursa(job #1804018)

Utilizator calin1Serban Calin calin1 Data 12 noiembrie 2016 09:58:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <cstdio>
#include <deque>
#include <climits>
#include <cstring>
#define N 500005
#define inf INT_MAX

using namespace std;

int n, k, vec[N];
char a[N * 7];

deque <int> dq;

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

void parsare()
{
    gets(a);

    int l = strlen(a);

    a[l] = ' ';

    int poz = 1;

    for(int i = 0 ; i < l ;)
    {
        int semn = 1;

        if(a[i] == '-')
        {
            semn = -1;
            i++;
        }

        int j;

        for(j = i ; a[j] != ' '; ++j)
        {
            vec[poz] = vec[poz] * 10 + (a[j] - '0');
        }

        vec[poz++] *= semn;

        i = j + 1;
    }
}

void citire()
{
    int maxim = -inf;

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

    int i_max = 1, j_max = k;

    parsare();

    for(int i = 1 ; i <= k - 1 ; ++i)
    {
        sterge(i);

        dq.push_back(i);
    }

    for(int i = k ; i <= n ; ++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()];

            j_max = i;
            i_max = i - k + 1;
        }
    }

    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;
}