#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
const int maxn = 9e4 + 5;
struct SegTree{
int st[maxn * 4];
int sz = 9e4;
void clear(){
memset(st, 0, sizeof(st));
}
void upd(int n, int l, int r, int ind, bool val ){
if(l == r){
st[n] = val;
return;
}
int mid = (l+r) /2;
if( mid >= ind)
upd(2*n+1, l, mid, ind,val);
else
upd(2*n+2, mid + 1, r, ind, val);
st[n] = st[2*n+1] + st[2*n+2];
}
void insert(int ind){
upd(0,1,sz, ind, 1);
}
void erase(int ind){
upd(0,1,sz, ind, 0);
}
int qry(int n, int l, int r, int k){
if(l == r)
{
return l;
}
int mid = (l+r) /2;
if(st[2*n+1]>=k){
return qry(2*n+1, l, mid , k);
}
else if(st[2*n+2] >=k - st[2*n+1]){
return qry(2*n+2, mid + 1,r, k - st[2*n+1]);
}
else
return -1;
}
int qry(int k){
return qry(0,1,sz, k);
}
};
/*
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]) {
SegTree active;
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 +1;
//cout << mid<<endl;
int ans = active.qry(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.qry(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.qry(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.qry(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.qry(mid));
}
}
//cout << endl;
}
return ans;
}
/***********/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1740 KB |
Output is correct |
2 |
Correct |
1 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1740 KB |
Output is correct |
2 |
Correct |
1 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
4 |
Correct |
18 ms |
2044 KB |
Output is correct |
5 |
Correct |
38 ms |
2124 KB |
Output is correct |
6 |
Correct |
12 ms |
2140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1740 KB |
Output is correct |
2 |
Correct |
1 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
4 |
Correct |
18 ms |
2044 KB |
Output is correct |
5 |
Correct |
38 ms |
2124 KB |
Output is correct |
6 |
Correct |
12 ms |
2140 KB |
Output is correct |
7 |
Correct |
996 ms |
3240 KB |
Output is correct |
8 |
Correct |
48 ms |
3660 KB |
Output is correct |
9 |
Correct |
1006 ms |
3676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1740 KB |
Output is correct |
2 |
Correct |
1 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
4 |
Correct |
18 ms |
2044 KB |
Output is correct |
5 |
Correct |
38 ms |
2124 KB |
Output is correct |
6 |
Correct |
12 ms |
2140 KB |
Output is correct |
7 |
Correct |
996 ms |
3240 KB |
Output is correct |
8 |
Correct |
48 ms |
3660 KB |
Output is correct |
9 |
Correct |
1006 ms |
3676 KB |
Output is correct |
10 |
Execution timed out |
5036 ms |
16228 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1740 KB |
Output is correct |
2 |
Correct |
1 ms |
1740 KB |
Output is correct |
3 |
Correct |
1 ms |
1740 KB |
Output is correct |
4 |
Correct |
18 ms |
2044 KB |
Output is correct |
5 |
Correct |
38 ms |
2124 KB |
Output is correct |
6 |
Correct |
12 ms |
2140 KB |
Output is correct |
7 |
Correct |
996 ms |
3240 KB |
Output is correct |
8 |
Correct |
48 ms |
3660 KB |
Output is correct |
9 |
Correct |
1006 ms |
3676 KB |
Output is correct |
10 |
Execution timed out |
5036 ms |
16228 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |