#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>
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;
struct Event {
int minn, row, diff;
};
bool operator < (Event fi, Event se) {
return fi.minn < se.minn;
}
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] = max(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] = min(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);
}*/
multiset<int> right_part;
forn(i, n) {
right_part.insert(prec[i][0].fi);
right_part.insert(prec[i][0].se);
}
/*for (int x : right_part) {
printf("start %d\n", x);
}*/
size_t pointer = 0;
vi rows(n);
while(pointer < events.size()) {
int minn = events[pointer].minn;
//printf("minn = %d\n", minn);
while(pointer < events.size() && events[pointer].minn == minn) {
int row = events[pointer].row;
/*if (rows[row] != m) {
right_part.erase(right_part.find(prec[row][rows[row]].fi));
right_part.erase(right_part.find(prec[row][rows[row]].se));
}*/
if (events[pointer].diff == +1) {
auto find_res = right_part.find(a[row][rows[row]]);
if (find_res != right_part.end())
right_part.erase(find_res);
}
else
right_part.insert(a[row][rows[row]]);
rows[row] += events[pointer].diff;
/*if (rows[row] != m) {
right_part.insert(prec[row][rows[row]].fi);
right_part.insert(prec[row][rows[row]].se);
}*/
pointer++;
}
/*for (int x : right_part) {
printf("now %d\n", x);
}*/
/*printf("minn = %d\n", minn);
forn(i, n)
printf("rows[%d] = %d\n", i, rows[i]);*/
if (right_part.empty())
return true;
int right_min = *right_part.begin();
int right_max = *right_part.rbegin();
if (right_max - right_min <= delta)
return true;
}
return false;
}
int solve() {
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 = global_max - global_min;
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]);
}
int first = solve();
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();
//printf("first = %d second = %d\n", first, second);
printf("%d", min(first, second));
}
Compilation message
joioi.cpp: In function 'int main()':
joioi.cpp:157: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:162: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 |
17 ms |
16120 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16228 KB |
Output is correct |
| 3 |
Correct |
18 ms |
16432 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16432 KB |
Output is correct |
| 5 |
Correct |
19 ms |
16432 KB |
Output is correct |
| 6 |
Incorrect |
18 ms |
16432 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
16120 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16228 KB |
Output is correct |
| 3 |
Correct |
18 ms |
16432 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16432 KB |
Output is correct |
| 5 |
Correct |
19 ms |
16432 KB |
Output is correct |
| 6 |
Incorrect |
18 ms |
16432 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
16120 KB |
Output is correct |
| 2 |
Correct |
18 ms |
16228 KB |
Output is correct |
| 3 |
Correct |
18 ms |
16432 KB |
Output is correct |
| 4 |
Correct |
17 ms |
16432 KB |
Output is correct |
| 5 |
Correct |
19 ms |
16432 KB |
Output is correct |
| 6 |
Incorrect |
18 ms |
16432 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
