Cod sursa(job #1760873)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 21 septembrie 2016 13:40:50
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

//ifstream fin("secventa.in");
ofstream fout("secventa.out");

int solution = -100000000, first, last, A[600010], N, K;
deque<int>deq;

int main()
{
    //fin >> N >> K;

    freopen("secventa.in", "r", stdin);

    scanf("%d%d", &N, &K);
    //freopen("secventa.out", "w", stdout);

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

    for(int i = 1; i <= N; i ++)
    {
        while( !deq.empty() && A[i] < A[deq.back()])
        {
            deq.pop_back();
        }

        deq.push_back(i);

        if(i - deq.front() >= K)
        {
            deq.pop_front();
        }

        if(i >= K && solution < A[deq.front()])
        {
            if(i - deq.front() < K - 1)
            {
                first = i - K + 1;
                last = i;
                solution = A[deq.front()];
            }
            else
            {
                first = deq.front();
                last = i;
                solution = A[deq.front()];
            }
        }
    }

    fout << first << " " << last << " " << solution;

    return 0;
}