//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("unroll-all-loops")
#include <bits/stdc++.h>
//#define TASK "lca"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define pb push_back
#define int long long
#define pii pair<int, int>
typedef long long ll;
//typedef long double ld;
using namespace std;
const int INF = 1e18;
const int MAXN = 1e8;
const int MOD = 1e9 + 7;
const double EPS = 1e-12;
const vector<int> dx = {1, 0, -1, 0, 0, 1, 0, -1};
//char buf[(int)1e9];
//size_t p_ = 0;
//
//inline void *operator new(size_t n_) {
// p_ += n_;
// return buf + p_ - n_;
//}
//inline void operator delete(void*) {};
ll power(ll x, ll n, ll mod = 1e9 + 7) {
if (n == 0) return 1ll;
if (n & 1ll) return power(x, n - 1ll, mod) * x % mod;
ll tmp = power(x, n >> 1ll, mod);
return (tmp * tmp) % mod;
}
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd (b, a % b);
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
int n, m;
map<pii, bool> used;
vector<vector<int>> g;
void go(pii p, set<pair<int, pii>> &next) {
for (int i = 0; i < 4; i++) {
int x = p.F + dx[i * 2];
int y = p.S + dx[i * 2 + 1];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
if (!used[{x, y}]) {
next.insert({g[x][y], {x, y}});
}
}
}
signed main() {
#ifndef LOCAL
#ifdef TASK
freopen(TASK".in", "r", stdin);
freopen(TASK".out", "w", stdout);
#endif
#endif
#ifdef LOCAL
//freopen("/Users/alekseygolub/Desktop/с++/ABS/ABS/input.txt", "r", stdin);
#endif
iostream::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
srand(924653523);
// == SOLUTION == //
cin >> n >> m;
int MIN = INF;
pii pos_min;
int MAX = -INF;
pii pos_max;
g.resize(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> g[i][j];
if (g[i][j] < MIN) {
MIN = g[i][j];
pos_min = {i, j};
}
if (g[i][j] > MAX) {
MAX = g[i][j];
pos_max = {i, j};
}
}
}
int ans1 = 0;
int ans2 = 0;
set<pii> side_a, side_b;
side_a.insert(pos_min);
side_b.insert(pos_max);
used[pos_max] = 1;
used[pos_min] = 1;
set<pair<int, pii>> next_a, next_b;
go(pos_max, next_b);
go(pos_min, next_a);
while(side_a.size() + side_b.size() != n * m) {
while (!next_a.empty() && used[(*next_a.begin()).S]) next_a.erase(next_a.begin());
while (!next_b.empty() && used[(*next_b.rbegin()).S]) next_b.erase(*next_b.rbegin());
if (next_a.empty() || next_b.empty()) break;
int test1 = max(ans1, abs(MIN - (*next_a.begin()).F));
int test2 = max(ans2, abs(MAX - (*next_b.rbegin()).F));
if (test1 < test2) {
ans1 = test1;
pii p = (*next_a.begin()).S;
side_a.insert(p);
used[p] = 1;
next_a.erase(next_a.begin());
go(p, next_a);
} else {
ans2 = test2;
pii p = (*next_b.rbegin()).S;
side_b.insert(p);
used[p] = 1;
next_b.erase(*next_b.rbegin());
go(p, next_b);
}
}
if (side_a.size() + side_b.size() != n * m && next_a.size()) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!used[{i, j}]) {
side_a.insert({i, j});
used[{i, j}] = 1;
}
}
}
}
if (side_a.size() + side_b.size() != n * m && next_b.size()) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!used[{i, j}]) {
side_b.insert({i, j});
used[{i, j}] = 1;
}
}
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (j != 0) cout << " ";
// if (used[{i, j}] && side_a.count({i, j})) cout << "1 ";
// if (used[{i, j}] && side_b.count({i, j})) cout << "2 ";
// if (!used[{i, j}]) cout << "- ";
// }
// cout << "\n";
// }
for (auto p: side_a) {
ans1 = max(ans1, abs(MIN - g[p.F][p.S]));
}
for (auto p: side_b) {
ans2 = max(ans2, abs(MAX - g[p.F][p.S]));
}
cout << max(ans1, ans2) << '\n';
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:114:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(side_a.size() + side_b.size() != n * m) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
joioi.cpp:139:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (side_a.size() + side_b.size() != n * m && next_a.size()) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
joioi.cpp:150:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (side_a.size() + side_b.size() != n * m && next_b.size()) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
552 KB |
Output is correct |
| 4 |
Correct |
2 ms |
552 KB |
Output is correct |
| 5 |
Correct |
2 ms |
552 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
692 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
552 KB |
Output is correct |
| 4 |
Correct |
2 ms |
552 KB |
Output is correct |
| 5 |
Correct |
2 ms |
552 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
692 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
488 KB |
Output is correct |
| 3 |
Correct |
2 ms |
552 KB |
Output is correct |
| 4 |
Correct |
2 ms |
552 KB |
Output is correct |
| 5 |
Correct |
2 ms |
552 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
692 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
