#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template <class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template <class T>
void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
template <class T>
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template <class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
const int MAX_N = 2010, inf = 1e9;
#define int ll
int n, m, a[MAX_N][MAX_N], res = inf;
struct bit {
vector<vector<int>> v;
int n, m;
bit(int _n, int _m) :
n(_n), m(_m), v(vector<vector<int>> (n+1, vector<int>(m+1, 0))) {
//v = vector<vector<int>> (n+1, vector<int>(m+1, 0));
//v.resize(n+1, vector<int>(m+1));
}
void add(int x, int y) {
for (int i = x;i <= n;i += i&-i)
for (int j = y;j <= m;j += j&-j)
++v[i][j];
}
int qry(int x, int y) {
int res = 0;
for (int i = x;i;i ^= i&-i)
for (int j = y;j;j ^= j&-j)
res += v[i][j];
return res;
}
};
void update() {
bit tree(n, m);
vector<pair<int,int>> id;
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
id.pb(i, j);
auto get = [&](pair<int,int> p) {
return a[p.first][p.second];
};
sort(AI(id), [&](auto x, auto y) {
return get(x) < get(y);
});
auto valid = [&](pair<int,int> p) {
assert(tree.qry(p.first, p.second) <= p.first * p.second);
return tree.qry(p.first, p.second) == p.first * p.second;
};
for (int i = 0, j = 0;i+1 < id.size();++i) {
tree.add(id[i].first, id[i].second);
while (j <= i && valid(id[j]))
++j;
//DE(get(id[i]), get(id[0]));
if (valid(id[0]) && valid(id[i]))
chmin(res, max(get(id[i]) - get(id[0]), get(id.back()) - get(id[j])));
}
chmin(res, get(id.back()) - get(id.front()));
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
cin >> a[i][j];
update();
for (int l = 1, r = n;l < r;++l, --r)
swap(a[l], a[r]);
update();
swap(n, m);
for (int i = 1;i <= n;++i)
for (int j = i+1;j <= m;++j)
swap(a[i][j], a[j][i]);
update();
for (int l = 1, r = n;l < r;++l, --r)
swap(a[l], a[r]);
update();
cout << res << '\n';
}
Compilation message
joioi.cpp: In constructor 'bit::bit(ll, ll)':
joioi.cpp:28:9: warning: 'bit::m' will be initialized after [-Wreorder]
28 | int n, m;
| ^
joioi.cpp:27:22: warning: 'std::vector<std::vector<long long int> > bit::v' [-Wreorder]
27 | vector<vector<int>> v;
| ^
joioi.cpp:29:2: warning: when initialized here [-Wreorder]
29 | bit(int _n, int _m) :
| ^~~
joioi.cpp: In function 'void update()':
joioi.cpp:70:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0, j = 0;i+1 < id.size();++i) {
| ~~~~^~~~~~~~~~~
joioi.cpp:30:57: warning: 'tree.bit::m' is used uninitialized in this function [-Wuninitialized]
30 | n(_n), m(_m), v(vector<vector<int>> (n+1, vector<int>(m+1, 0))) {
| ^
joioi.cpp:30:40: warning: 'tree.bit::n' may be used uninitialized in this function [-Wmaybe-uninitialized]
30 | n(_n), m(_m), v(vector<vector<int>> (n+1, vector<int>(m+1, 0))) {
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
288 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
288 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
288 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
