#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
#include <unordered_set>
using namespace std;
#define INF 1e+9
#define mp make_pair
#define pb push_back
#define fi first
#define fs first
#define se second
#define i64 long long
#define li long long
#define lint long long
#define pii pair<int, int>
#define vi vector<int>
#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)
const int maxn = 2005;
const int inf = 1e9+7;
pii prec[maxn][maxn];
int n, m;
int a[maxn][maxn];
int b[maxn][maxn];
int global_min, global_max;
vi pos_min;
//unordered_set<int> possible_min;
struct Event {
int minn, row, diff;
};
bool operator < (Event fi, Event se) {
return fi.minn < se.minn;
}
inline bool check(int delta) {
//fprintf(stderr, "check %d\n", delta);
vector<Event> events;
vi app_limits(m, -inf);
vi dis_limits(m, inf);
forn(i, n) {
int cur_app = -inf;
int cur_dis = inf;
forn(j, m) {
//min <= x <= min + delta
cur_app = max(cur_app, a[i][j] - delta);
cur_app = max(cur_app, app_limits[j]);
app_limits[j] = cur_app;
cur_dis = min(cur_dis, a[i][j] + 1);
cur_dis = min(cur_dis, dis_limits[j]);
dis_limits[j] = cur_dis;
if (cur_app < cur_dis) {
events.pb({cur_app, i, +1});
events.pb({cur_dis, i, -1});
}
}
}
sort(events.begin(), events.end());
/*for (auto e : events) {
fprintf(stderr, "event minn = %d row = %d diff = %d\n", e.minn, e.row, e.diff);
}*/
size_t pointer = 0;
vi rows(n);
int cur_pos = 0;
while(pointer < events.size()) {
int minn = events[pointer].minn;
while(pointer < events.size() && events[pointer].minn == minn) {
rows[events[pointer].row] += events[pointer].diff;
pointer++;
}
while(cur_pos < (int)pos_min.size() && pos_min[cur_pos] <= minn)
cur_pos++;
if (pointer < events.size()) {
if (cur_pos < (int)pos_min.size() && pos_min[cur_pos] > events[pointer].minn)
continue;
}
//if (possible_min.find(minn) == possible_min.end())
// continue;
/*printf("minn = %d\n", minn);
forn(i, n)
printf("rows[%d] = %d\n", i, rows[i]);*/
int len = rows[0];
int right_min = inf;
int right_max = -inf;
forn(row, n) {
len = min(len, rows[row]);
right_min = min(right_min, prec[row][len].fi);
right_max = max(right_max, prec[row][len].se);
if (right_max - right_min > delta)
break;
}
//fprintf(stderr, "right min = %d max = %d\n", right_min, right_max);
if (right_max - right_min <= delta)
return true;
}
return false;
}
int solve(int upper) {
forn(i, n) {
prec[i][m] = {inf, -inf};
for (int len = m - 1; len >= 0; --len) {
prec[i][len] = {min(prec[i][len + 1].fi, a[i][len]),
max(prec[i][len + 1].se, a[i][len])};
//printf("prec[%d][%d] = %d %d\n", i, len, prec[i][len].fi, prec[i][len].se);
}
}
int start = 0;
int finish = upper;
while(start < finish) {
int middle = (start + finish) / 2;
if (check(middle)) {
finish = middle;
} else {
start = middle + 1;
}
}
return start;
}
int main() {
#ifdef LOCAL
freopen("inp", "r", stdin);
//freopen("outp", "w", stdout);
#else
// freopen(TASKNAME ".in", "r", stdin);
// freopen(TASKNAME ".out", "w", stdout);
#endif
scanf("%d%d", &n, &m);
global_min = inf;
global_max = -inf;
forn(i, n)
forn(j, m) {
scanf("%d", &a[i][j]);
global_min = min(global_min, a[i][j]);
global_max = max(global_max, a[i][j]);
}
forn(i, n)
forn(j, m)
pos_min.pb(a[i][j]);
sort(pos_min.begin(), pos_min.end());
pos_min.resize(unique(pos_min.begin(), pos_min.end()) - pos_min.begin());
/*forn(i, n)
forn(j, m)
possible_min.insert(a[i][j]);*/
int first = solve(global_max - global_min);
forn(i, n)
forn(j, m)
b[n - i - 1][j] = a[i][j];
memcpy(a, b, sizeof(b));
/*forn(i, n) {
forn(j, m)
printf("%d ", b[i][j]);
printf("\n");
}*/
int second = solve(first);
//printf("first = %d second = %d\n", first, second);
printf("%d", min(first, second));
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
joioi.cpp:152:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i][j]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
16120 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16232 KB |
Output is correct |
| 3 |
Correct |
18 ms |
16232 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
16232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
16120 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16232 KB |
Output is correct |
| 3 |
Correct |
18 ms |
16232 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
16232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
16120 KB |
Output is correct |
| 2 |
Correct |
17 ms |
16232 KB |
Output is correct |
| 3 |
Correct |
18 ms |
16232 KB |
Output is correct |
| 4 |
Incorrect |
19 ms |
16232 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
