Cod sursa(job #1159877)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 29 martie 2014 22:28:46
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <deque>

using namespace std;
#define DIM 1000000
char buff[DIM];
int poz=DIM-1;

void citeste(int &numar)
{
    numar = 0;
    int signum = 1;
    while( (buff[poz] < '0' || buff[poz] > '9') && buff[poz] != '-')
        if (++poz == DIM) fread(buff,1,DIM,stdin),poz=0;
    while('0'<=buff[poz] && buff[poz]<='9' || buff[poz] == '-')
    {
        if(buff[poz] == '-')signum = -1;
        else numar = numar*10 + buff[poz] - 48;
        if (++poz == DIM) fread(buff,1,DIM,stdin),poz=0;
    }
    numar *= signum;
}

int N,K,v[500005];
deque<int> Q;

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

    citeste(N);
    citeste(K);
    int BEST = -999999,li,lf;

    for(int i = 1; i <= N; ++i)citeste(v[i]);
    for(int i = 1; i <= N; ++i)
    {
        while(!Q.empty() && v[Q.back()] > v[i])
            Q.pop_back();
        Q.push_back(i);
        if(Q.front() <= i-K)
            Q.pop_front();
        if(v[Q.front()] > BEST && i >= K)
        {
            BEST = v[Q.front()];
            li = i-K+1;
            lf = i;
        }
    }
    printf("%d %d %d\n",li,lf,BEST);
    return 0;
}