Cod sursa(job #1621279)

Utilizator feli2felicia iuga feli2 Data 29 februarie 2016 18:01:24
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <iostream>
#include <fstream>

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

int rmq[20][500005], lg[500005], n, k, i, j, q, mx, mxi, mxj;

int query(int poz, int lung)
{
    int poz_sf=poz+lung-1;
    int put=lg[lung];
    return min(rmq[put][poz], rmq[put][poz_sf-(1<<put)+1]);
}

int main()
{
    fin>>n>>k;
    for(i = 1;i <= n; i++)
    {
        fin>>rmq[0][i];
    }
    for(i = 2; (1<<i) <= k; i++)
    {
        lg[i]=lg[i/2]+1;
    }
    for(i = 1; i <= lg[k]; i++)
    {
        for(j = 1; j+(1<<i)<n; j++)
        {
            rmq[i][j]=min(rmq[i-1][j], rmq[i-1][j+(1<<(i-1))]);
        }
    }
    for(i = 1; i <= n-k+1; i++)
    {
        q=query(i,k);
        if(q>mx)
        {
            mx=q;
            mxi=i;
            mxj=i+k-1;
        }
    }
    fout<<mxi<<" "<<mxj<<" "<<mx;
    return 0;
}