#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
vector<int> cmp;
int getID (int targ) {
return lower_bound(all(cmp), targ) - cmp.begin();
}
const int mn = 4e6 + 6;
int lo[2002][2002], hi[2002][2002], loCol[2002][2002], hiCol[2002][2002];
int calcLo[mn], calcHi[mn], bound[2002];
vector<pii> contain[mn];
bool ok (int i, int j) {
return j < bound[i];
}
bool check (int delta) {
int pos = -1, curLo = INT_MAX, curHi = INT_MIN;
for (int k = 0; k < cmp.size(); k++) {
while (pos + 1 < cmp.size() && cmp[pos + 1] < cmp[k] - delta) {
pos++;
for (auto [row, col] : contain[pos]) {
curLo = min(curLo, lo[row][col]);
curHi = max(curHi, hi[row][col]);
}
}
int cHi = max(calcHi[k], curHi);
int cLo = min(calcLo[k], curLo);
if (cHi != INT_MIN && cLo != INT_MAX && cHi - cLo <= delta) return 1;
}
return 0;
}
int solve (vector<vector<int>> &vec, int n, int m) {
vector<vector<int>> loCol(n + 1, vector<int>(m + 1));
vector<vector<int>> hiCol(n + 1, vector<int>(m + 1));
vector<vector<int>> hiRow(n + 1, vector<int>(m + 1));
for (int j = 1; j <= m; j++) {
int curLo = INT_MAX, curHi = INT_MIN;
for (int i = n; i >= 1; i--) {
loCol[i][j] = curLo = min(curLo, vec[i][j]);
hiCol[i][j] = curHi = max(curHi, vec[i][j]);
}
}
for (int i = 1; i <= n; i++) {
int curLo = INT_MAX, curHi = INT_MIN;
//lo[i][0] = curLo, hi[i][0] = curHi;
for (int j = 1; j <= m; j++) {
lo[i][j] = curLo = min(curLo, loCol[i][j]);
hi[i][j] = curHi = max(curHi, hiCol[i][j]);
}
curHi = INT_MIN;
for (int j = m; j >= 1; j--)
hiRow[i][j] = curHi = max(curHi, vec[i][j]);
}
priority_queue<tt> pqLo, pqHi;
for (int i = 1; i <= n; i++) {
bound[i] = m + 1;
for (int j = 1; j <= m; j++) {
pqLo.push(make_tuple(-lo[i][j], i, j));
pqHi.push(make_tuple( hi[i][j], i, j));
contain[getID(vec[i][j])].push_back({i, j});
}
}
for (int k = 0; k < cmp.size(); k++) {
for (auto [row, col] : contain[k])
while (bound[row] > 1 && hiRow[row][bound[row] - 1] <= cmp[k]) bound[row]--;
while (pqLo.size()) {
int val, i, j; tie(val, i, j) = pqLo.top();
if (ok(i, j)) break;
else pqLo.pop();
}
while (pqHi.size()) {
int val, i, j; tie(val, i, j) = pqHi.top();
if (ok(i, j)) break;
else pqHi.pop();
}
calcLo[k] = (pqLo.size() ? -get<0>(pqLo.top()) : INT_MAX);
calcHi[k] = (pqHi.size() ? get<0>(pqHi.top()) : INT_MIN);
}
int ans = 0;
if (!check(0)) {
for (int i = 4; i >= 0; i--) {
int mask = ans | (1 << i);
if (!check(mask)) ans |= (1 << i);
}
ans++;
}
for (int k = 0; k < cmp.size(); k++)
contain[k].clear();
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<int>> vec(n + 1, vector<int>(m + 1));
vector<vector<int>> rot(m + 1, vector<int>(n + 1));
//cmp.push_back(0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> vec[i][j];
rot[j][n - i + 1] = vec[i][j];
cmp.push_back(vec[i][j]);
}
}
sort(all(cmp)); filter(cmp);
cout << min(solve(vec, n, m), solve(rot, m, n));
return 0;
}
Compilation message
joioi.cpp: In function 'bool check(int)':
joioi.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int k = 0; k < cmp.size(); k++) {
| ~~^~~~~~~~~~~~
joioi.cpp:31:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | while (pos + 1 < cmp.size() && cmp[pos + 1] < cmp[k] - delta) {
| ~~~~~~~~^~~~~~~~~~~~
joioi.cpp:33:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | for (auto [row, col] : contain[pos]) {
| ^
joioi.cpp: In function 'int solve(std::vector<std::vector<int> >&, int, int)':
joioi.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int k = 0; k < cmp.size(); k++) {
| ~~^~~~~~~~~~~~
joioi.cpp:81:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for (auto [row, col] : contain[k])
| ^
joioi.cpp:107:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for (int k = 0; k < cmp.size(); k++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
100952 KB |
Output is correct |
| 2 |
Correct |
16 ms |
100956 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
100956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
100952 KB |
Output is correct |
| 2 |
Correct |
16 ms |
100956 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
100956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
100952 KB |
Output is correct |
| 2 |
Correct |
16 ms |
100956 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
100956 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
