#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <list>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
using namespace std;
const int maxn = 2020;
const int kokn = 390;
const int MOd = 1e9+7;
typedef long long Lint;
typedef long double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int a, b;
struct fenwick{
int fw[maxn];
int v = 0;
void clear() {
for(int i=1;i<=max(a,b);i++) fw[i] = 0;
}
void up( int x, int y ) {
if( v ) {
x = b - x + 1;
y = a - x + 1;
}
for(int i=x;i>0;i-=i&(-i)) umax( fw[i], y );
}
int find( int x ) {
if( v ) {
x = b - x + 1;
}
int t = 0;
for(int i=x;i<=a;i+=i&(-i)) umax( t, fw[i] );
return t;
}
}l, r;
int ar[maxn][maxn];
vector<iii> v;
int fw[maxn], maxi, mini;
void rot() {
for(int i=0;i<v.size();i++) {
v[i].se = ii( b-v[i].se.se+1, v[i].se.fi );
ar[v[i].se.fi][v[i].se.se] = v[i].fi;
}
swap( a, b );
}
int calc() {
l.clear();
r.clear();
int lo = 0, loc = 1;
int hi = 1e9, hic = 1;
int i=0,j=v.size()-1;
while( i <= j ) {
if( loc && maxi - v[i].fi >= v[j].fi-mini ) {
int x = v[i].se.fi;
int y = v[i].se.se;
int v = r.find( y );
if( x+v > a ) {
loc = 0;
continue;
}
l.up( y, x );
i++;
} else if( hic ) {
int x = v[j].se.fi;
int y = v[j].se.se;
int v = l.find( y );
if( x <= v ) {
hic = 0;
continue;
}
r.up( y, x );
j--;
} else break;
}
return max( maxi-v[i].fi, v[j].fi-mini );
}
int main()
{
//freopen("asd.in","r",stdin);
scanf("%d %d",&a,&b);
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
scanf("%d",&ar[i][j]), v.pb( iii( ar[i][j], ii( i, j )) );
r.v = 1;
sort( all( v ) );
maxi = v[v.size()-1].fi;
mini = v[0].fi;
int ans = 1e9;
for(int i=0;i<4;i++) {
//printf("asd %d\n",i);
umin( ans, calc( ) );
rot();
}
cout << ans << endl;
}
Compilation message
joioi.cpp: In function 'void rot()':
joioi.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++) {
^
joioi.cpp: In function 'int calc()':
joioi.cpp:79:9: warning: unused variable 'lo' [-Wunused-variable]
int lo = 0, loc = 1;
^
joioi.cpp:80:9: warning: unused variable 'hi' [-Wunused-variable]
int hi = 1e9, hic = 1;
^
joioi.cpp: In function 'int main()':
joioi.cpp:112:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&a,&b);
^
joioi.cpp:116:70: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&ar[i][j]), v.pb( iii( ar[i][j], ii( i, j )) );
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
17984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
17984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
17984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
