# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
866654 | 2023-10-26T15:38:58 Z | nasir_bashirov | Quality Of Living (IOI10_quality) | C++17 | 1 ms | 2396 KB |
#include "quality.h" #include <bits/stdc++.h> using namespace std; #define db long double #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define endl '\n' #define all(x) x.begin(), x.end() #define fastio\ ios_base::sync_with_stdio(0);\ cin.tie(0);\ cout.tie(0)\ struct fenwickTree{ int n; vi BIT; fenwickTree(int sz){ n = sz; BIT.resize(n + 1, 0); } void update(int i, int v){ if(i == 0) return; while(i <= n){ BIT[i] += v; i += i & (-i); } } int query(int l, int r){ if(l > r) return 0; if(l != 1) return query(1, r) - query(1, l - 1); int res = 0; while(r > 0){ res += BIT[r]; r -= r & (-r); } return res; } }; int rectangle(int r, int c, int h, int w, int Q[3001][3001]) { int res = 1e9; for(int i = 1; i <= r - h + 1; i++){ fenwickTree t(r * c); for(int a = 1; a < w; a++){ for(int b = i; b <= i + h - 1; b++){ t.update(Q[b][a], 1); } } for(int a = w; a <= c; a++){ for(int b = i; b <= i + h - 1; b++){ t.update(Q[b][a], 1); } if(a > w){ for(int b = i; b <= i + h - 1; b++){ t.update(Q[b][a - w], -1); } } int lx = 1, rx = r * c, med; while(lx <= rx){ // cout << lx << " " << rx << endl; int mid = (lx + rx) / 2; if(t.query(1, mid) >= h * w / 2 + 1){ med = mid; rx = mid - 1; } else{ lx = mid + 1; } } // cout << i << " " << a - w + 1 << " " << med << endl; res = min(res, med); } } return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Incorrect | 1 ms | 2396 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |