#include <bits/stdc++.h>
//#include "quality.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using set_ = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
const int maxn = 9e6 + 5;
/*
int getmedian(){
int cnt = 0;
int median = -1;
for(int a : active){
if(cnt == active.size() / 2){
median = a;
break;
}
cnt++;
}
return median;
}
*/
set_<int> active;
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 mid = (H * W ) /2 ;
//cout << mid<<endl;
int ans = *active.find_by_order(mid);
//cout << active.qry(mid)<<endl;
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, *active.find_by_order(mid));
}
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, *active.find_by_order(mid));
}
}
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, *active.find_by_order(mid));
}
//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, *active.find_by_order(mid));
}
}
//cout << endl;
}
return ans;
}
/***********/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 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 |
332 KB |
Output is correct |
4 |
Correct |
30 ms |
844 KB |
Output is correct |
5 |
Correct |
59 ms |
764 KB |
Output is correct |
6 |
Correct |
17 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 |
332 KB |
Output is correct |
4 |
Correct |
30 ms |
844 KB |
Output is correct |
5 |
Correct |
59 ms |
764 KB |
Output is correct |
6 |
Correct |
17 ms |
972 KB |
Output is correct |
7 |
Correct |
2112 ms |
3128 KB |
Output is correct |
8 |
Correct |
105 ms |
3788 KB |
Output is correct |
9 |
Correct |
1906 ms |
2568 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 |
332 KB |
Output is correct |
4 |
Correct |
30 ms |
844 KB |
Output is correct |
5 |
Correct |
59 ms |
764 KB |
Output is correct |
6 |
Correct |
17 ms |
972 KB |
Output is correct |
7 |
Correct |
2112 ms |
3128 KB |
Output is correct |
8 |
Correct |
105 ms |
3788 KB |
Output is correct |
9 |
Correct |
1906 ms |
2568 KB |
Output is correct |
10 |
Execution timed out |
5045 ms |
19988 KB |
Time limit exceeded |
11 |
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 |
332 KB |
Output is correct |
4 |
Correct |
30 ms |
844 KB |
Output is correct |
5 |
Correct |
59 ms |
764 KB |
Output is correct |
6 |
Correct |
17 ms |
972 KB |
Output is correct |
7 |
Correct |
2112 ms |
3128 KB |
Output is correct |
8 |
Correct |
105 ms |
3788 KB |
Output is correct |
9 |
Correct |
1906 ms |
2568 KB |
Output is correct |
10 |
Execution timed out |
5045 ms |
19988 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |