#include <bits/stdc++.h>
using namespace std;
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 2002
ii n, m, a;
pair<ii,ii> p[maxn];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
//freopen("in.in", "r", stdin);
//freopen("out.out", "w", stdout);
cin >> n >> m;
ii mn = INFii;
ii mx = 0;
vector<pair<ii,pair<ii,ii>>> pq1,pq2;
for(ii i = 1; i <= n; i++) {
for(ii j = 1; j <= m; j++) {
cin >> a;
pq1.pb(mp(a,mp(i,j)));
pq2.pb(mp(a,mp(i,j)));
mn = min(mn,a);
mx = max(mx,a);
}
}
sort(all(pq1));
sort(all(pq2),greater<pair<ii,pair<ii,ii>>>());
if(mn == mx) {
cout << 0 << endl;
return 0;
}
// com minimo na esquerda:
ii l = 0;
ii r = 1e9+1;
ii ans1;
while(l <= r) {
ii mid = (l+r)/2;
for(ii i = 1; i <= n; i++) {
p[i].fr = 0;
p[i].sc = m+1;
}
for(ii i = 0; i < pq2.size() && pq2[i].fr-mn >= mid; i++) {
auto x = pq2[i].sc;
p[x.fr].sc = min(p[x.fr].sc,x.sc-1);
}
for(ii i = 0; i < pq1.size() && mx-pq1[i].fr >= mid; i++) {
auto x = pq1[i].sc;
p[x.fr].fr = max(p[x.fr].fr,x.sc);
}
//ver se ta crescente/decrescente
ii actc = 0; bool okc = 1;
ii actd = m+1; bool okd = 1;
for(ii i = 1; i <= n; i++) {
actc = max(actc,p[i].fr);
if(actc > p[i].sc || p[i].fr > p[i].sc) okc = 0;
actd = min(actd,p[i].sc);
if(actd < p[i].fr || p[i].fr > p[i].sc) okd = 0;
}
if(okc || okd) {
//se deu bom com esse (l+r)/2 quero abaixar o (l+r)/2
ans1 = (l+r)/2-1;
r = (l+r)/2-1;
}
else {
l = (l+r)/2+1;
}
}
//com mx na esquerda
l = 0;
r = 1e9+1;
ii ans2;
while(l <= r) {
ii mid = (l+r)/2;
for(ii i = 1; i <= n; i++) {
p[i].fr = 0;
p[i].sc = m+1;
}
for(ii i = 0; i < pq2.size() && pq2[i].fr-mn >= mid; i++) {
auto x = pq2[i].sc;
p[x.fr].fr = max(p[x.fr].fr,x.sc);
}
for(ii i = 0; i < pq1.size() && mx-pq1[i].fr >= mid; i++) {
auto x = pq1[i].sc;
p[x.fr].sc = min(p[x.fr].sc,x.sc-1);
}
//ver se ta crescente/decrescente
ii actc = 0; bool okc = 1;
ii actd = m+1; bool okd = 1;
for(ii i = 1; i <= n; i++) {
actc = max(actc,p[i].fr);
if(actc > p[i].sc || p[i].fr > p[i].sc) okc = 0;
actd = min(actd,p[i].sc);
if(actd < p[i].fr || p[i].fr > p[i].sc) okd = 0;
}
if(okc || okd) {
//se deu bom com esse (l+r)/2 quero abaixar o (l+r)/2
ans1 = (l+r)/2-1;
r = (l+r)/2-1;
}
else {
l = (l+r)/2+1;
}
}
cout << min(ans1,ans1) << endl;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:66:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(ii i = 0; i < pq2.size() && pq2[i].fr-mn >= mid; i++) {
| ~~^~~~~~~~~~~~
joioi.cpp:73:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(ii i = 0; i < pq1.size() && mx-pq1[i].fr >= mid; i++) {
| ~~^~~~~~~~~~~~
joioi.cpp:115:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(ii i = 0; i < pq2.size() && pq2[i].fr-mn >= mid; i++) {
| ~~^~~~~~~~~~~~
joioi.cpp:121:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(ii i = 0; i < pq1.size() && mx-pq1[i].fr >= mid; i++) {
| ~~^~~~~~~~~~~~
joioi.cpp:105:8: warning: unused variable 'ans2' [-Wunused-variable]
105 | ii ans2;
| ^~~~
joioi.cpp:10:14: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
10 | #define endl '\n'
| ^~~~
joioi.cpp:57:8: note: 'ans1' was declared here
57 | ii ans1;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
