#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
//long long rtamx = __INT_MAX__;
struct SegTree{
long long dd, htt, val1, mid;
SegTree *L, *R;
SegTree(long long l, long long r){
dd=l, htt=r;
val1=0;
mid=(dd+htt)/2;
if(l!=r){
L=new SegTree(l, mid);
R=new SegTree(mid+1, r);
}
}
int query(long long val){
if(dd==htt){
cout<<" "<< dd<<endl;
return dd;
}
if(val<=L->val1){
return L->query(val);
}else{
return R->query(val-L->val1);
}
}
void insert(int pos, int val){
if(dd==htt){
cout<<dd<<endl;
val1+=val;
return ;
}
if(pos<=mid){
L->insert(pos, val);
}else{
R->insert(pos, val);
}
val1=L->val1+R->val1;
}
};
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int rtamx;
SegTree *tree = new SegTree(0, R*C+1);
bool up = true, creado = true;
for(int x = 0 ; x < H ; x++){
for(int y = 0 ; y < W ; y++){
tree->insert(Q[x][y], 1);
}
}
int xd = (((H*W)+1)/2);
rtamx=tree->query(xd);
for(int i = 0 ; i <= R-H ; i++){
//cout<<"i"<<" "<<i<<endl;
if(up){
for(int j = 1 ; j <= C-W ; j++){
//cout<<"j"<<" "<<j<<endl;
for(int x = i ; x < i+H ; x++){
tree->insert(Q[x][j-1], -1);
tree->insert(Q[x][(j+W)-1], 1);
}
rtamx=min(rtamx, tree->query(xd));
}
creado=true;
//C-W
if((i+1<=R-H)){
for(int x = C-W ; x < C ; x++){
tree->insert(Q[i][x], -1);
tree->insert(Q[(i+H)][x], 1);
}
rtamx=min(rtamx, tree->query(xd));
}
}else{
for(int j = ((C-W)-1) ; j >=0 ; j--){
//cout<<"j"<<" "<<j<<endl;
for(int x = i ; x < i+H ; x++){
tree->insert(Q[x][j], 1);
tree->insert(Q[x][(j+W)], -1);
}
}
rtamx=min(rtamx, tree->query(xd));
if((i+1<=R-H)){
for(int x = 0 ; x < W ; x++){
tree->insert(Q[i][x], -1);
tree->insert(Q[(i+H)][x], 1);
}
rtamx=min(rtamx, tree->query(xd));
}
}
up=!up;
}
//cout<<rtamx<<endl;
return rtamx;
}
Compilation message
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:46:18: warning: variable 'creado' set but not used [-Wunused-but-set-variable]
46 | bool up = true, creado = true;
| ^~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
460 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |