Cod sursa(job #3299388)

Utilizator Tudor_11Tudor Ioan Calin Tudor_11 Data 5 iunie 2025 20:29:41
Problema Plantatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("plantatie.in");
ofstream fout("plantatie.out");
int rmq[505][505][10];
int p2[505];
int main()
{
    int n,m;
    fin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            fin>>rmq[i][j][0];
        }
    }
    p2[0]=1;
    p2[1]=1;
    for(int i=2;i<=n;i++)
    {
        p2[i]=p2[i/2]+1;
    }
    for(int k=1;(1<<k)<=n;k++)
    {
        for(int i=0;i+(1<<k)-1<n;i++)
        {
            for(int j=0;j+(1<<k)-1<n;j++)
            {
                rmq[i][j][k]=max({rmq[i][j][k-1],rmq[i][j+(1<<(k-1))][k-1],rmq[i+(1<<(k-1))][j][k-1],rmq[i+(1<<(k-1))][j+(1<<(k-1))][k-1]});
            }
        }
    }
    int x,y,k;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>k;
        x--;
        y--;
        int l=p2[k];
        fout<<max({rmq[x][y][l],rmq[x][y+k-(1<<l)][l],rmq[x+k-(1<<l)][y][l],rmq[x+k-(1<<l)][y+k-(1<<l)][l]})<<'\n';
    }
    return 0;
}