Cod sursa(job #2614340)

Utilizator xXoctavianXxStanescu Matei Octavian xXoctavianXx Data 11 mai 2020 17:05:07
Problema Plantatie Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,m;
int rmq[502][502][10];

void create()
{
    int stop=log2(n);
    for(int k=1; k<=stop; k++)
    {
        int r=n-(1<<k)+1;
        for(int i=1; i<=r; i++)
        {
            for(int j=1; j<=r; j++)
            {
                rmq[i][j][k]=max(rmq[i][j][k-1], rmq[i][j+(1<<(k-1))][k-1]);
                int r2=max(rmq[i+(1<<(k-1))][j][k-1], rmq[i+(1<<(k-1))][j+(1<<(k-1))][k-1]);
                rmq[i][j][k]=max(rmq[i][j][k],r2);
            }
        }
    }
}

int query(int i, int j, int l)
{
    int k=log2(l);
    int r1=max(rmq[i][j][k], rmq[i][j+l-(1<<k)][k]);
    int r2=max(rmq[i+l-(1<<k)][j][k],rmq[i+l-(1<<k)][j+l-(1<<k)][k]);
    return max(r1,r2);
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            fin>>rmq[i][j][0];
        }
    }
    create();
    int i,j,k;
    for(;m>0; m--)
    {
        fin>>i>>j>>k;
        fout<<query(i,j,k)<<"\n";
    }
    return 0;
}