| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 390103 | MilosMilutinovic | 삶의 질 (IOI10_quality) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* author: milos
* created: 15.04.2021 12:17:56
**/
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
template <typename T>
class fenwick2d {
public:
vector< vector<T> > fenw;
int n, m;
fenwick2d(int _n, int _m) : n(_n), m(_m) {
fenw.resize(n);
for (int i = 0; i < n; i++) {
fenw[i].resize(m);
}
}
inline void modify(int i, int j, T v) {
int x = i;
while (x < n) {
int y = j;
while (y < m) {
fenw[x][y] += v;
y |= (y + 1);
}
x |= (x + 1);
}
}
inline T get(int i, int j) {
T v{};
int x = i;
while (x >= 0) {
int y = j;
while (y >= 0) {
v += fenw[x][y];
y = (y & (y + 1)) - 1;
}
x = (x & (x + 1)) - 1;
}
return v;
}
};
int rectangle(int n, int m, int h, int w, vector<vector<int>> a) {
vector<int> xs;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
xs.push_back(a[i][j]);
}
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = lower_bound(xs.begin(), xs.end(), a[i][j]) - xs.begin();
}
}
auto InRect = [&](int l, int r, int ll, int rr, int x, int y) {
return l <= x && x <= ll && r <= y && y <= rr;
};
auto Can = [&](int x) {
vector<vector<int>> b(n, vector<int>(m));
fenwick2d<int> fenw(n, m);
int xx = -1, yy = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] <= x) {
b[i][j] = 1;
} else {
b[i][j] = 0;
}
if (a[i][j] == x) {
xx = i; yy = j;
}
fenw.modify(i, j, b[i][j]);
}
}
assert(xx != -1 && yy != -1);
int P = h * w;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int ii = i + h - 1, jj = j + w - 1;
if (ii >= n || jj >= m || !InRect(i, j, ii, jj, xx, yy)) {
continue;
}
int sum = fenw.get(ii, jj) - fenw.get(i - 1, jj) - fenw.get(ii, j - 1) + fenw.get(i - 1, j - 1);
if (sum >= (P + 1) / 2) {
return true;
}
}
}
return false;
};
int bot = 0, top = (int) xs.size() - 1, ans = 0;
while (bot <= top) {
int mid = bot + top >> 1;
if (Can(mid)) {
top = mid - 1;
ans = mid;
} else {
bot = mid + 1;
}
}
return xs[ans];
}