#include <bits/stdc++.h> using namespace std; // Global declarations (used to replace vectors inside the function) typedef long long ll; ll inf = 2000000000000; // Using lg array for the temporary calculations int lg[3001][3001], pref[3001][3001]; /** * Finds the minimum median value in any sub-rectangle of size h x w * within the given matrix q of size r x c. * * The median is the smallest value M such that the number of elements * greater than M is less than or equal to the number of elements less than or equal to M. * This function uses Binary Search on the answer (the median value). * For a chosen candidate median 'm', it checks if any h x w sub-rectangle * has a majority of elements (i.e., more than half) less than or equal to 'm'. */ int rectangle(int r, int c, int h, int w, int q[3001][3001]) { // Note: The global array 'lg' is used here instead of a local vector<vector<int>>vece int (*vece)[3001] = lg; int l1 = 1, r1 = r * c; int dodajemo; while (l1 < r1) { // Binary search on the median value 'm' ll m = (l1 + r1) / 2; bool moze = false; // 1. Calculate a 2D prefix sum (vece) based on the current candidate median 'm' // vece[i][j] stores the sum of (1 if q[x][y] <= m, -1 otherwise) for all 0 <= x <= i, 0 <= y <= j. for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (q[i][j] <= m) { dodajemo = 1; // Count as 'good' } else { dodajemo = -1; // Count as 'bad' } // Standard 2D Prefix Sum calculation if (i == 0 && j == 0) { vece[i][j] = dodajemo; } else if (i == 0) { vece[i][j] = vece[i][j - 1] + dodajemo; } else if (j == 0) { vece[i][j] = vece[i - 1][j] + dodajemo; } else { vece[i][j] = vece[i - 1][j] + vece[i][j - 1] - vece[i - 1][j - 1] + dodajemo; } // 2. Check the h x w sub-rectangle ending at (i, j) if (i + 1 >= h && j + 1 >= w) { // Current sub-rectangle is from (i - h + 1, j - w + 1) to (i, j) int ima = vece[i][j]; // Sum for the rectangle from (0, 0) to (i, j) // Subtract contributions from outside the target h x w rectangle if (i >= h) { // Subtract the area above the target rectangle ima -= vece[i - h][j]; } if (j >= w) { // Subtract the area to the left of the target rectangle ima -= vece[i][j - w]; } if (i >= h && j >= w) { // Add back the top-left corner that was subtracted twice ima += vece[i - h][j - w]; } // 'ima' is the number of (elements <= m) minus the number of (elements > m) // in the current h x w sub-rectangle. // If ima > 0, it means the number of elements <= m is greater than the number of // elements > m. This confirms 'm' could be the median (or smaller). if (ima > 0) { moze = true; // No need to check further sub-rectangles for this 'm' break; } } } if (moze) break; } // Binary Search update if (moze) { // 'm' is a possible median, try for a smaller one r1 = m; } else { // 'm' is too small, need a larger median l1 = m + 1; } } // l1 will converge to the minimum median value return l1; } // You can keep the rest of your program logic here. // The main function and input/output were not provided, so I'm only showing the modified function.