#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
set<int> active;
int getmedian(){
int cnt = 0;
int median = -1;
for(int a : active){
if(cnt == active.size() / 2){
median = a;
break;
}
cnt++;
}
return median;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
active.clear();
for(int top = 0; top < H; top ++){
for(int left = 0; left < W; left++ ){
active.insert(Q[top][left]);
}
}
int ans = getmedian();
for(int top = 0; top <= R - H; top++){
//cout << top <<":\n";
//if top % 2 === 0, we go from left to right
if(top % 2 == 0){
if(top > 0){
for(int left = 0; left < W; left++ ){
active.erase(Q[top - 1][left]);
active.insert(Q[top + H - 1][left]);
}
ans = min(ans, getmedian());
}
for(int left = 1; left <=C - W;left++){
//iterate left boundary of rectangle
//cout << left << "->";
for(int t = top; t < top + H; t++){
active.erase(Q[t][left - 1]);
active.insert(Q[t][left + W - 1]);
}
ans = min(ans, getmedian());
}
}
else{
if(top > 0){
for(int right = C - 1; right >= C - W; right-- ){
active.erase(Q[top - 1][right]);
active.insert(Q[top + H - 1][right]);
}
ans = min(ans, getmedian());
}
//we go from right to left
for(int right = C - 2; right >=W - 1; right--){
//cout << right <<"->";
//iterate left boundary of rectangle
for(int t = top; t < top + H; t++){
active.erase(Q[t][right + 1]);
active.insert(Q[t][right - W +1]);
}
ans = min(ans, getmedian());
}
}
//cout << endl;
}
return ans;
}
/***********/
Compilation message
quality.cpp: In function 'int getmedian()':
quality.cpp:11:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | if(cnt == active.size() / 2){
| ~~~~^~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
63 ms |
848 KB |
Output is correct |
5 |
Correct |
64 ms |
716 KB |
Output is correct |
6 |
Correct |
30 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
63 ms |
848 KB |
Output is correct |
5 |
Correct |
64 ms |
716 KB |
Output is correct |
6 |
Correct |
30 ms |
972 KB |
Output is correct |
7 |
Execution timed out |
5062 ms |
3652 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
63 ms |
848 KB |
Output is correct |
5 |
Correct |
64 ms |
716 KB |
Output is correct |
6 |
Correct |
30 ms |
972 KB |
Output is correct |
7 |
Execution timed out |
5062 ms |
3652 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
63 ms |
848 KB |
Output is correct |
5 |
Correct |
64 ms |
716 KB |
Output is correct |
6 |
Correct |
30 ms |
972 KB |
Output is correct |
7 |
Execution timed out |
5062 ms |
3652 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |