// thsi submission is hilariously wrong
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)
#define NN 2010
#define M 1000000007 // 998244353
ll numValid; // init to rows+columns
struct counter {
ll mex = 0, sz = 0;
bitset<NN> see;
void update(ll idx) {
assert(!see[idx]);
numValid -= mex == sz;
sz++;
see[idx] = 1;
while (see[mex]) ++mex;
numValid += mex == sz;
}
} rows[NN], cols[NN];
ll ccs = 0;
ll to(ll i, ll j){
return i * NN + j;
}
//DSU
ll parent[NN*NN], sz[NN*NN];
ll find(ll a){ return a == parent[a] ? a : parent[a] = find(parent[a]); }
void merge(ll u, ll v) {
u = find(u), v=find(v);
if (u!=v) {
if (sz[u]<sz[v]) swap(u, v);
sz[u] += sz[v];
parent[v] = u;
ccs--;
}
}
bool filled[NN][NN];
bool vfront[NN*NN], vback[NN*NN];
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
G(n) G(m)
vector<pair<ll, pl>> a;
F(i, 0, n) {
F(j, 0, m) {
G(x) a.emplace_back(x, pl{i, j});
}
}
ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0, -1, 0, 1};
sort(A(a));
ll ans = a.back().K - a.begin()->K;
{
ccs = 0;
F(i, 0, NN) F(j, 0, NN) {
filled[i][j] = sz[to(i, j)] = 1;
parent[to(i, j)] = to(i, j);
}
F(idx, 0, a.size()) {
auto [i, j] = a[idx].V;
filled[i][j] = 1; ccs++;
F(k, 0, 4) {
ll ni = i + dx[k], nj = j + dy[k];
if (min(ni, nj) >= 0 and ni < n and nj < m and filled[ni][nj]) {
merge(to(ni, nj), to(i, j));
}
}
vfront[idx] = ccs==1;
}
}
{
ccs = 0;
F(i, 0, NN) F(j, 0, NN) {
filled[i][j] = sz[to(i, j)] = 1;
parent[to(i, j)] = to(i, j);
}
for (ll idx = ll(a.size())-1; idx >= 0; --idx) {
auto [i, j] = a[idx].V;
filled[i][j] = 1; ccs++;
F(k, 0, 4) {
ll ni = i + dx[k], nj = j + dy[k];
if (min(ni, nj) >= 0 and ni < n and nj < m and filled[ni][nj]) {
merge(to(ni, nj), to(i, j));
}
}
vback[idx] = ccs==1;
}
}
F(k, 0, n)
numValid = n+m;
F(idx, 0, a.size()) {
auto [i, j] = a[idx].V;
rows[i].update(j); cols[j].update(i);
if (numValid == n+m and vfront[idx] and vback[idx+1]) {
ans = min(ans,
max(a[idx].K - a.begin()->K, a.back().K - a[idx+1].K)
);
}
}
cout << ans << '\n';
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:84:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
84 | filled[i][j] = sz[to(i, j)] = 1;
| ~~~~~~~~~~~~~^~~
joioi.cpp:22:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | #define F(i, l, r) for (ll i = (l); i < r; ++i)
......
88 | F(idx, 0, a.size()) {
| ~~~~~~~~~~~~~~~~
joioi.cpp:88:9: note: in expansion of macro 'F'
88 | F(idx, 0, a.size()) {
| ^
joioi.cpp:103:41: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
103 | filled[i][j] = sz[to(i, j)] = 1;
| ~~~~~~~~~~~~~^~~
joioi.cpp:22:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | #define F(i, l, r) for (ll i = (l); i < r; ++i)
......
122 | F(idx, 0, a.size()) {
| ~~~~~~~~~~~~~~~~
joioi.cpp:122:5: note: in expansion of macro 'F'
122 | F(idx, 0, a.size()) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
72280 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
72144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
72280 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
72144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
72280 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
72144 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
