Cod sursa(job #2623686)

Utilizator raluca1234Tudor Raluca raluca1234 Data 3 iunie 2020 16:39:55
Problema Plantatie Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
// RMQ 2D
#include <iostream>
#include <fstream>
#include <cmath>

const int MAX_N = 5e2 + 1;
const int MAX_LOG_N = 18;

int v[MAX_N][MAX_N];
int rmq[MAX_N][MAX_N][MAX_LOG_N];
	
int main()
{
    std::ifstream fin("plantatie.in");
    std::ofstream fout("plantatie.out");

    int n, m;	
    fin >> n >> m;
	
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            fin >> v[i][j]; 
        }
    }
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            rmq[i][j][0] = v[i][j];
        }
    }
	
    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) {
                int maximum = rmq[i][j][k - 1];
                maximum = std::max(maximum, rmq[i][j + (1 << (k - 1))][k - 1]);
                maximum = std::max(maximum, rmq[i + (1 << (k - 1))][j][k - 1]);
                maximum = std::max(maximum, rmq[i + (1 << (k - 1))][j + (1 << (k - 1))][k - 1]);
                rmq[i][j][k] = maximum;
            }
        }
    }
	
    while (m--) {
        int x_topleft, y_topleft, square_side_length;
    
        fin >> x_topleft >> y_topleft >> square_side_length;

        x_topleft--;
        y_topleft--;

        int k = (int)log2(square_side_length);

        int answer = rmq[x_topleft][y_topleft][k];
        answer = std::max(answer, rmq[x_topleft][y_topleft + square_side_length - (1 << k)][k]);
	    answer = std::max(answer, rmq[x_topleft + square_side_length - (1 << k)][y_topleft][k]);
        answer = std::max(answer, rmq[x_topleft + square_side_length - (1 << k)][y_topleft + square_side_length - (1 << k)][k]);
	
        fout << answer << '\n';
    }

    return 0;	
}