#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 2200
ii n, m, a[maxn][maxn];
map<ii,vector<pair<ii,ii>>> val;
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;
for(ii i = 1; i <= n; i++) {
for(ii j = 1; j <= m; j++) {
cin >> a[i][j];
val[a[i][j]].pb(mp(i,j));
mn = min(mn,a[i][j]);
mx = max(mx,a[i][j]);
}
}
if(mn == mx) {
cout << 0 << endl;
return 0;
}
vector<pair<pair<ii,ii>,vector<pair<ii,ii>>>> pq;
for(auto x : val) {
pq.pb(mp(mp(x.fr-mn,0),x.sc));
pq.pb(mp(mp(mx-x.fr,1),x.sc));
}
sort(all(pq), greater<pair<pair<ii,ii>,vector<pair<ii,ii>>>>());
// 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;
}
for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {
ii tp = pq[i].fr.sc;
for(auto x : pq[i].sc) {
if(tp == 1) { // tem que ta junto com o mn
p[x.fr].fr = max(p[x.fr].fr,x.sc);
}
else {
p[x.fr].sc = min(p[x.fr].sc,x.sc-1);
}
}
}
//ver se ta crescente/decrescente
ii actc = 1; bool okc = 1;
ii actd = m; 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 mid quero abaixar o mid
ans1 = mid-1;
r = mid-1;
}
else {
l = mid+1;
}
}
//com mx na esquerda
for(ii i = 0; i < pq.size(); i++) {
pq[i].fr.sc^= 1;
}
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;
}
for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {
ii tp = pq[i].fr.sc;
for(auto x : pq[i].sc) {
if(tp == 1) { // tem que ta junto com o mn
p[x.fr].fr = max(p[x.fr].fr,x.sc);
}
else {
p[x.fr].sc = min(p[x.fr].sc,x.sc-1);
}
}
}
//ver se ta crescente/decrescente
ii actc = 1; bool okc = 1;
ii actd = m; 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 mid quero abaixar o mid
ans2 = mid-1;
r = mid-1;
}
else {
l = mid+1;
}
}
cout << min(ans1,ans2) << endl;
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:69:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {
| ~~^~~~~~~~~~~
joioi.cpp:106:21: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(ii i = 0; i < pq.size(); i++) {
| ~~^~~~~~~~~~~
joioi.cpp:121:25: warning: comparison of integer expressions of different signedness: 'ii' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, std::vector<std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(ii i = 0; i < pq.size() && pq[i].fr.fr >= mid; i++) {
| ~~^~~~~~~~~~~
joioi.cpp:112:8: warning: 'ans2' may be used uninitialized in this function [-Wmaybe-uninitialized]
112 | ii ans2;
| ^~~~
joioi.cpp:60:8: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
60 | ii ans1;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
0 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
