#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#include "quality.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef string str;
vector<int> fwt;
void dodaj(int x,int koliko){
for(;x<fwt.size();x+=x&-x) fwt[x]+=koliko;
}
int upit(int x){
int ret=0;
for(;x>0;x-=x&-x) ret+=fwt[x];
return ret;
}
int tren(int H,int W){
int l=1;
int r=fwt.size();
//cout<<" "<<upit(fwt.size()-1)<<endl;
while(l<=r){
int mid=l+(r-l)/2;
int sta=upit(mid);
if(sta>W*H/2+1){
r=mid-1;
}else if(sta==W*H/2+1){
return mid;
}else{
l=mid+1;
}
}
}
void uradi(int i1,int i2,int j,int koliko,int** novoQ){
for(;i1<=i2;i1++){
dodaj(novoQ[i1][j],koliko);
}
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
int ret=INT_MAX;
fwt.resize(R*C+1,0);
int** novoQ=new int*[3001];
for(int i=0;i<=3000;i++){
novoQ[i]=new int[3001];
}
for(int i=0;i<=3000;i++){
for(int j=0;j<3000;j++) novoQ[i][j]=Q[i][j];
}
for(int i=0;i<R-H;i++){
for(int j=0;j<W;j++){
uradi(i,i+H-1,j,1,novoQ);
}
ret=min(ret,tren(H,W));
//cout<<i<<" "<<W-1<<" "<<tren(H,W)<<endl;
for(int j=W;j<C;j++){
uradi(i,i+H-1,j-W,-1,novoQ);
uradi(i,i+H-1,j,1,novoQ);
ret=min(ret,tren(H,W));
//cout<<i<<" "<<j<<" "<<tren(H,W)<<endl;
}
for(int j=C-1;j>=C-W;j--){
uradi(i,i+H-1,j,-1,novoQ);
//cout<<i<<" "<<j<<" "<<tren(H,W)<<endl;
}
}
return ret;
}
Compilation message
quality.cpp: In function 'void dodaj(int, int)':
quality.cpp:30:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(;x<fwt.size();x+=x&-x) fwt[x]+=koliko;
| ~^~~~~~~~~~~
quality.cpp: In function 'int tren(int, int)':
quality.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
54 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35840 KB |
Output is correct |
2 |
Correct |
29 ms |
35832 KB |
Output is correct |
3 |
Correct |
29 ms |
35832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35840 KB |
Output is correct |
2 |
Correct |
29 ms |
35832 KB |
Output is correct |
3 |
Correct |
29 ms |
35832 KB |
Output is correct |
4 |
Incorrect |
42 ms |
36216 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35840 KB |
Output is correct |
2 |
Correct |
29 ms |
35832 KB |
Output is correct |
3 |
Correct |
29 ms |
35832 KB |
Output is correct |
4 |
Incorrect |
42 ms |
36216 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35840 KB |
Output is correct |
2 |
Correct |
29 ms |
35832 KB |
Output is correct |
3 |
Correct |
29 ms |
35832 KB |
Output is correct |
4 |
Incorrect |
42 ms |
36216 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
35840 KB |
Output is correct |
2 |
Correct |
29 ms |
35832 KB |
Output is correct |
3 |
Correct |
29 ms |
35832 KB |
Output is correct |
4 |
Incorrect |
42 ms |
36216 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |