Cod sursa(job #2122685)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 5 februarie 2018 13:29:17
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
#include<vector>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int N,V[500003],P[20]= {0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144},K,Max=-10000000,Poz1,Poz2;
vector < int > Min[20];

int main()
{
    fin>>N>>K;
    for(int i=1; i<=N; i++)
        fin>>V[i];
    for(int i=1; i<=N-1; i++)
        Min[1].push_back(min(V[i],V[i+1]));
    for(int i=2; i<=18; i++)
    {
        if(N-P[i]+1<0)
            break;
        for(int j=0; j<N-P[i]+1; j++)
            Min[i].push_back(min(Min[i-1][j],Min[i-1][j+P[i]/2]));
    }
    if(K==1)
    {
        for(int i=1; i<=N; i++)
            if(V[i]>Max)
            {
                Max=V[i];
                Poz1=i;
            }
        fout<<Poz1<<" "<<Poz1<<" "<<Max<<"\n";
    }
    else
    {
        int Search;
        for(int i=1; i<=18; i++)
            if(K>=P[i])
                Search=i;
        for(int i=1; i<=N-K+1; i++)
            if(min(Min[Search][i-1],Min[Search][i+K-P[Search]-1])>Max)
            {
                Poz1=i;
                Max=min(Min[Search][i-1],Min[Search][i+K-P[Search]-1]);
            }
        fout<<Poz1<<" "<<Poz1+K-1<<" "<<Max<<'\n';
    }


}