Cod sursa(job #2485014)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 31 octombrie 2019 21:24:07
Problema Plantatie Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <cstdio>

using namespace std;

int n, m;
int a[755][755], r[755][755][11], log[755];

void gen_log() {
  int last_base = 1;

  log[1] = 0;
  for(int i = 2; i <= n; i++)
    if(i == 2 * last_base) {
      log[i] = log[last_base] + 1;
      last_base *= 2;
    }
    else
      log[i] = log[last_base];
}

void rmq() {
  for(int k = 0; k <= log[n]; k++)
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++) /// r[i][j][k] = maximul din matricea patratica de latura 2^k, pt care coltul stanga-sus se afla la coord (i, j)
        if(k == 0)
          r[0][i][j] = a[i][j];
        else
          r[k][i][j] = max(max(r[k - 1][i][j], r[k - 1][i][j + (1 << (k - 1))]),
                           max(r[k - 1][i + (1 << (k - 1))][j], r[k - 1][i + (1 << (k - 1))][j + (1 << (k - 1))]));
}

int main() {
  freopen("plantatie.in", "r", stdin);
  freopen("plantatie.out", "w", stdout);
  int x, y, l, k;

  scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      scanf("%d", &a[i][j]);

  gen_log();
  rmq();

  for(int i = 1; i <= m; i++) {
    scanf("%d %d %d", &x, &y, &l);
    k = log[l];
    printf("%d\n", max(max(r[k][x][y], r[k][x][y + l - (1 << k)]),
                     max(r[k][x + l - (1 << k)][y], r[k][x + l - (1 << k)][y + l - (1 << k)])));
  }

  return 0;
}