Cod sursa(job #972525)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 11 iulie 2013 22:35:58
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");
struct Element{
int value;
int begin;
};
int minimum_result[21][500002],log[500002],Arr[500002],N,K;
Element Secv[500002];
void Calculate_log2()
{
    int i=2,next=2;
    while(i<=N)
    {
        if(i!=next)
            log[i]=log[i-1];
        else
        {
            log[i]=log[i-1]+1;
            next=i*2;
        }
        i++;
    }
}
void Read()
{
    f>>N>>K;
    int i;
    for(i=1;i<=N;i++)
    {
        f>>Arr[i];
        minimum_result[0][i]=Arr[i];
    }
}
void Build_matrichs()
{
    int i,j,forward=1;
    for(i=1;i<=log[N];i++)
    {
        for(j=1;j<=N-forward*2+1;j++)
            minimum_result[i][j]=min(minimum_result[i-1][j],minimum_result[i-1][j+forward]);
        forward*=2;
    }
}
int power(int x,int y)
{
    int i,p=1;
    for(i=1;i<=y;i++)
        p*=x;
    return(p);
}
int RMQ(int x,int y)
{
    int i;
    int how_much=log[y-x+1];
    if(log[y-x]==how_much-1)
        return minimum_result[log[y-x+1]][x];
    else
        return min(minimum_result[how_much][x],minimum_result[how_much][y-power(2,how_much)+1]);
}
void Solve()
{
    int i=1,sum,maximum=-30001;
    Secv[K].value=RMQ(1,K);
    Secv[K].begin=1;
    i=K+1;
    while(i<=N)
    {
        if(RMQ(Secv[i-1].begin,i)<RMQ(i-K+1,i))
        {
            Secv[i].value=RMQ(i-K+1,i);
            Secv[i].begin=i-K+1;
        }
        else
        {
            Secv[i].value=RMQ(Secv[i-1].begin,i);
            Secv[i].begin=Secv[i-1].begin;
        }
        i++;
    }
    int result_begin,result_end;
    for(i=K;i<=N;i++)
    {
        if(maximum<Secv[i].value)
        {
            maximum=Secv[i].value;
            result_begin=Secv[i].begin;
            result_end=i;
        }
    }
    g<<result_begin<<" "<<result_end<<" "<<maximum<<"\n";
}
int main()
{
    Read();
    Calculate_log2();
    Build_matrichs();
    Solve();
    return 0;
}