#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.
