Cod sursa(job #1288873)

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

const int NMAX = 500010, INF = 0x3f3f3f3f;

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

const int MaxB = 8192;
char Buf[MaxB];
int Ptr;

int Get()
{
    int Nr = 0;
    while(!isdigit(Buf[Ptr]))
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    while(isdigit(Buf[Ptr]))
    {
        Nr = Nr * 10 + Buf[Ptr] - '0';
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    return Nr;
}

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

    N = Get(); K = Get();
    for(int i = 1; i <= N; ++ i)
    {
        A[i] = Get();

        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 = i - K + 1, End = i;
        }
    }
    printf("%i %i %i\n", Start, End, Min);
}