Cod sursa(job #1984199)

Utilizator FredyLup Lucia Fredy Data 23 mai 2017 23:01:12
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>

using namespace std;

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

#define lim 500010
#define loglim 20
int n,k,rmq[loglim][lim],maxx,st,dr;
short log[lim];

int main()
{
    fin>>n>>k;
    for(int i=1; i<=n; i++)
        fin>>rmq[0][i];
    for(int i=2; i<=n; i++)
        log[i]=log[i>>1]+1;

    for(int k=1; (1<<k)<=n; k++)
        for(int j=1; j+(1<<k)-1<=n; j++)
            rmq[k][j]=min(rmq[k-1][j],rmq[k-1][j+(1<<(k-1))]);

    int l,aux;
    maxx=-1000000000;
    for(int i=1; i<=n-k+1; i++)
        for(int j=k+1; j<=n; j++)
        {
            l=log[j-i+1];
            aux=min(rmq[l][i],rmq[l][j-(1<<l)+1]);
            if(maxx<=aux)
            {
                if(maxx==aux && j-i+1>dr-st+1)
                {
                    st=i;
                    dr=j;
                }
                if(maxx<aux)
                {
                    maxx=aux;
                    st=i;
                    dr=j;
                }
            }
        }

    fout<<st<<' '<<dr<<' '<<maxx;

    fin.close();
    fout.close();
    return 0;
}