Cod sursa(job #1736348)

Utilizator llalexandruLungu Alexandru Ioan llalexandru Data 1 august 2016 16:40:59
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#define MAX 10000

using namespace std;

struct qq{int val; int id;};

qq deq[500005];

int n, k, i, bk, fr, x, fi;
int sum;
char f[MAX];
int sign, pos;

void citeste(int &nr)
{
    nr=0;
    sign=0;
     while(f[pos]<'0'||f[pos]>'9')
     {
         if(f[pos]=='-')
             sign=1;
        pos++;
        if(pos==MAX)
            fread(f,1,MAX,stdin),pos=0;
     }
    while(f[pos]>='0'&&f[pos]<='9')
    {
        nr=nr*10+f[pos++]-'0';
        if(pos==MAX)
            fread(f,1,MAX,stdin),pos=0;
    }
    if(sign==1)
        nr=-nr;
}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    fread(f,1,MAX,stdin);
    citeste(n);
    citeste(k);
    fr=1; bk=0;
    deq[0].val=(-1)*1000000;
    sum=(-1)*1000000;
    for (i=1; i<=n; i++)
    {
        citeste(x);
        while (bk >= fr && deq[bk].val>=x)
            bk--;
        deq[++bk].val=x;
        deq[bk].id=i;
        while (fr <= bk && deq[fr].id<=i-k)
            fr++;
        if (k<=i)
        {
            if(deq[fr].val>sum)
            {
                sum=deq[fr].val;
                fi=i;
            }
        }
    }
     printf("%i %i %i",fi-k+1,fi,sum);
    return 0;
}