Solution of the this problem -> https://codeforces.com/contest/1301/problem/E

sol.cc

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define rep(i,a,n) for (int i=a;i<n;i++)

constexpr ll p = 1000000007;
constexpr int R = 0, G = 1, B = 2, Y = 3;
constexpr int N = 500, LOGN = 9;

int sparse_table[N][N][LOGN][LOGN];
int log_dist[N + 1];


bool check_size(int sx, int sy, int size, vector<vector<char>> &vec) {
    int n = vec.size(), m = vec[0].size();
    if(sx < 0 || sy < 0 || sx + 2 * size > n || sy + 2 * size > m) return false;

    int hx = sx + size, hy = sy + size;

    // Check the vertical sides
    for(int i = sx; i < sx + 2 * size; i++) {
        vector<int> js = {sy, sy + 2 * size - 1};
        for(const auto j : js) {
            if(i < hx && j < hy && vec[i][j] != 'R') return false;
            if(i < hx && j >= hy && vec[i][j] != 'G') return false;
            if(i >= hx && j < hy && vec[i][j] != 'Y') return false;
            if(i >= hx && j >= hy && vec[i][j] != 'B') return false;
        }
    }

    // Check the horizontal sides
    for(int j = sy; j < sy + 2 * size; j++) {
        vector<int> is = {sx, sx + 2 * size - 1};
        for(const auto i : is) {
            if(i < hx && j < hy && vec[i][j] != 'R') return false;
            if(i < hx && j >= hy && vec[i][j] != 'G') return false;
            if(i >= hx && j < hy && vec[i][j] != 'Y') return false;
            if(i >= hx && j >= hy && vec[i][j] != 'B') return false;
        }
    }

    return true;
}

void find_squares(vector<vector<char>> &vec) {
    int n = vec.size(), m = vec[0].size();
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < m - 1; j++)
        {
            if(vec[i][j] != 'R') continue;
            int size = 1;
            int sx = i, sy = j;
            while(check_size(sx, sy, size, vec)) {
                size++;
                sx = i - size + 1;
                sy = j - size + 1;
            }
            size--;
            sparse_table[i][j][0][0] = size;
        }
    }
}

void calc_sparse_table() {
    for(int l1 = 1; l1 < LOGN; l1++) {
        for(int i = 0; i + (1 << l1) <= N; i++) {
            int ishift = i + (1 << (l1 - 1));
            rep(j, 0, N) {
                sparse_table[i][j][l1][0] = max(sparse_table[i][j][l1 - 1][0], sparse_table[ishift][j][l1 - 1][0]);
            }
        }
    }

    for(int l2 = 1; l2 < LOGN; l2++) {
        for(int j = 0; j + (1 << l2) <= N; j++) {
            int jshift = j + (1 << (l2 - 1));
            rep(i, 0, N) {
                sparse_table[i][j][0][l2] = max(sparse_table[i][j][0][l2 - 1], sparse_table[i][jshift][0][l2 - 1]);
            }
        }
    }

    for(int lsum = 1; lsum < 2 * LOGN; lsum++) {
        for(int l1 = 1; l1 < lsum; l1++) {
            int l2 = lsum - l1;
            if(max(l1, l2) >= LOGN) continue;
            for(int i = 0; i + (1 << l1) <= N; i++) {
                for(int j = 0; j + (1 << l2) <= N; j++) {
                    int ishift = i + (1 << (l1 - 1));
                    int jshift = j + (1 << (l2 - 1));
                    sparse_table[i][j][l1][l2] = max(sparse_table[i][j][l1][l2], sparse_table[i][j][l1 - 1][l2 - 1]);
                    sparse_table[i][j][l1][l2] = max(sparse_table[i][j][l1][l2], sparse_table[i][jshift][l1 - 1][l2 - 1]);
                    sparse_table[i][j][l1][l2] = max(sparse_table[i][j][l1][l2], sparse_table[ishift][j][l1 - 1][l2 - 1]);
                    sparse_table[i][j][l1][l2] = max(sparse_table[i][j][l1][l2], sparse_table[ishift][jshift][l1 - 1][l2 - 1]);
                }
            }
        }
    }
}

void calc_log() {
    log_dist[1] = 0;
    rep(i, 2, N + 1) {
        log_dist[i] = log_dist[i / 2] + 1; 
    }
}

int rmq(int x1, int y1, int x2, int y2) {  // rmq here stands for "range maximum query"
    int xlog = log_dist[x2 - x1 + 1];
    int ylog = log_dist[y2 - y1 + 1];
    int xright = x2 - (1 << xlog) + 1;
    int yright = y2 - (1 << ylog) + 1;

    vector<int> tmp{
        sparse_table[x1][y1][xlog][ylog],
        sparse_table[xright][y1][xlog][ylog],
        sparse_table[x1][yright][xlog][ylog],
        sparse_table[xright][yright][xlog][ylog],
    };

    return *max_element(tmp.begin(), tmp.end());
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<char>> vec(n, vector<char>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> vec[i][j];
        }
    }
    memset(sparse_table, 0, sizeof(sparse_table[0][0][0][0]) * N * N * LOGN * LOGN);
    find_squares(vec);
    calc_sparse_table();
    calc_log();

    rep(i, 0, q) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2 -= 2; y2 -= 2;
        if(x2 < x1 || y2 < y1 || rmq(x1, y1, x2, y2) == 0) {
            cout << 0 << endl;
            continue;
        }
        int low = 0, high = min((x2 - x1) / 2, (y2 - y1) / 2);
        if(rmq(x1 + high, y1 + high, x2 - high, y2 - high) >= high + 1) {
            cout << 4 * (high + 1) * (high + 1) << endl;
            continue;
        }
        while(high - low > 1) {
            int dist = (low + high) / 2;
            if(rmq(x1 + dist, y1 + dist, x2 - dist, y2 - dist) >= dist + 1) {
                low = dist;
            } else {
                high = dist;
            }
        }
        cout << 4 * (low + 1) * (low + 1) << endl;
    }

    return 0;
}