Cod sursa(job #1288867)

Utilizator RaduVisanRadu Visan RaduVisan Data 9 decembrie 2014 09:30:43
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
#include <deque>
using namespace std;

const int NMAX = 500010, INF = 0x3f3f3f3f;

int N, K, A[NMAX], Min = -INF, Start = INF, End = INF;
deque<int> D;

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

    scanf("%i %i", &N, &K);
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i", &A[i]);

        while(!D.empty() && A[D.back()] >= A[i]) D.pop_back();
        D.push_back(i);
        while(!D.empty() && D.front() <= i - K) D.pop_front();
        if(!D.empty() && i >= K)
        {
            int CrtMin = A[D.front()];
            if(CrtMin > Min) Min = CrtMin, Start = D.front(), End = i;
            else if(CrtMin == Min && D.front() < Start) Start = D.front(), End = i;
        }
    }
    printf("%i %i %i\n", Start, End, Min);
}