#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int H, W;
vector<pair<int, ii> > arr;
int ans = (int)1e9+7;
int fw1[2049], fw2[2049];
int fw1get(int pos) {
pos += 1;
int mxmm = -1;
while (pos <= 2048) {
mxmm = max(mxmm, fw1[pos]);
pos += pos & -pos;
}
return mxmm;
}
int fw2get(int pos) {
pos += 1;
int mxmm = -1;
while (pos <= 2048) {
mxmm = max(mxmm, fw2[pos]);
pos += pos & -pos;
}
return mxmm;
}
void fw1max(int pos, int val) {
pos += 1;
while (pos > 0) {
fw1[pos] = max(fw1[pos], val);
pos -= pos & -pos;
}
}
void fw2max(int pos, int val) {
pos += 1;
while (pos > 0) {
fw2[pos] = max(fw2[pos], val);
pos -= pos & -pos;
}
}
void calc() {
for (int i = 0; i < 2049; i++) {
fw1[i] = -1;
fw2[i] = -1;
}
int i = 0, j = arr.size()-1;
if (arr[j].second.first <= arr[i].second.first && arr[j].second.second <= arr[i].second.second) ;
fw1max(arr[i].second.second, arr[i].second.first);
fw2max(W-arr[j].second.second-1, H - arr[j].second.first - 1);
int mini = arr[i].first, maxi = arr[j].first;
int worst1 = 0, worst2 = 0;
while (true) {
worst1 = arr[j-1].first - mini;
worst2 = maxi - arr[i+1].first;
if (j == i+1) break;
if (worst1 < worst2) {
i++;
ii pos = arr[i].second;
int wall = fw2get(W-pos.second-1);
if (pos.first >= H - wall - 1) break;
fw1max(pos.second, pos.first);
}
else {
j--;
ii pos = arr[j].second;
int wall = fw1get(pos.second);
if (pos.first <= wall) break;
fw2max(W-pos.second-1, H - pos.first - 1);
}
}
//cerr << i << "," << j << " " << worst1 << " " << worst2 << endl;
ans = min(ans, max(worst1, worst2));
}
void rotate() {
for (int i = 0; i < arr.size(); i++) {
arr[i].second = mp(arr[i].second.second, H-arr[i].second.first-1);
}
H = H ^ W;
W = H ^ W;
H = H ^ W;
}
void dump() {
int mat[H][W];
for (int i = 0; i < arr.size(); i++) {
mat[arr[i].second.first][arr[i].second.second] = arr[i].first;
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cerr << mat[i][j] << " ";
} cerr << endl;
}
}
int main(int argc, char **argv) {
//freopen("input", "r", stdin);
//freopen("output", "w", stdout);
scanf("%d%d", &H, &W);
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
int x; scanf("%d", &x);
arr.pb(mp(x, mp(i, j)));
}
}
sort(arr.begin(), arr.end());
calc();
rotate();
//dump();
calc();
rotate();
//dump();
calc();
rotate();
//dump();
calc();
printf("%d\n", ans);
return 0;
}
Compilation message
joioi.cpp: In function 'void rotate()':
joioi.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); i++) {
^
joioi.cpp: In function 'void dump()':
joioi.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < arr.size(); i++) {
^
joioi.cpp: In function 'int main(int, char**)':
joioi.cpp:110:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &H, &W);
^
joioi.cpp:113:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x; scanf("%d", &x);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
2040 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
