#include "quality.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int matrix[3001][3001], n, m, r, c;
int arr[3001][3001];
int sum[3001][3001], mat[3001][3001];
bool solve(int fix, int fx, int fy)
{
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(matrix[i][j] > fix)
mat[i][j] = 1;
else if(matrix[i][j] < fix)
mat[i][j] = -1;
else
mat[i][j]=0;
}
}
sum[0][0] = mat[0][0];
for (int j = 1; j < m; j++) {
sum[0][j] = mat[0][j] + sum[0][j - 1];
}
for (int i = 1; i < n; i++) {
sum[i][0] = mat[i][0] + sum[i - 1][0];
}
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1]
- sum[i - 1][j - 1];
}
}
int total;
for (int i = r - 1; i < n; i++)
{
for (int j = c - 1; j < m; j++)
{
total = sum[i][j];
if (i - r >= 0) {
total = total - sum[i - r][j];
}
if (j - c >= 0) {
total = total - sum[i][j - c];
}
if (i - r >= 0 && j - c >= 0) {
total = total + sum[i -r][j - c];
}
if(total == 0 && fx <= i && fy <= j) {
return true;
}
}
}
return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
n = R;
m = C;
r = H;
c = W;
vi arr1;
map<int, pii> mapa;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
matrix[i][j] = Q[i][j];
arr1.pb(Q[i][j]);
mapa[Q[i][j]] = mp(i,j);
}
sort(arr1.begin(), arr1.end());
int l = 0, r = arr1.size() - 1, mid,rez;
while(l <= r){
mid = (l + r) / 2;
bool check = solve(arr1[mid], mapa[arr1[mid]].first, mapa[arr1[mid]].second);
if(check){
rez = mid;
r = mid - 1;
}
else
l = mid + 1;
}
return arr1[rez];
}/*
int main(){
int a, b, c, d;
cin>>a>>b>>c>>d;
for(int i = 0; i < a; i++){
for(int j = 0; j < b; j++)
cin>>arr[i][j];
}
cout<<rectangle(a, b, c, d)<<endl;
return 0;
}*/
Compilation message
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:89:17: warning: 'rez' may be used uninitialized in this function [-Wmaybe-uninitialized]
89 | return arr1[rez];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
876 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |