Pagini recente » Cod sursa (job #524548) | Cod sursa (job #334229) | Cod sursa (job #3256927) | Cod sursa (job #682853) | Cod sursa (job #2616105)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("plantatie.in");
ofstream cout("plantatie.out");
const int nmax=505;
int n,m;
int logg[nmax],rmq[nmax][nmax][35];
void read()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>rmq[i][j][0];
}
void log2func()
{
logg[1]=0;
for(int i=2;i<=n;i++)
logg[i]=1+logg[i/2];
}
void sparseT()
{
for(int l=1;l<=logg[n];l++)
{
int k=(1<<(l-1));
for(int i=(1<<l);i<=n;i++)
for(int j=(1<<l);j<=n;j++)
rmq[i][j][l]=max({rmq[i][j][l-1],rmq[i-k][j][l-1],rmq[i][j-k][l-1],rmq[i-k][j-k][l-1]});
}
}
void queries()
{
while(m--)
{
int l,p,i,j,k;
cin>>i>>j>>k;
i+=k-1;
j+=k-1;
l=logg[k];
p=(1<<l);
cout<<max({rmq[i][j][l],rmq[i-k+p][j][l],rmq[i][j-k+p][l],rmq[i-k+p][j-k+p][l]})<<"\n";
}
}
int main()
{
read();
log2func();
sparseT();
queries();
return 0;
}