1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| #include <bits/stdc++.h> #define int long long #define ll long long using namespace std;
const int N = 1e3 + 66, inf = 1234567891011;
int n, m, lim, lin, ron, res = inf, a[N][N]; int q[N], Q[N]; int rmax[N][N], rmin[N][N], cmax[N][N], cmin[N][N];
signed main() { int i, j, l, r, L, R; n = read(), m = read(), lim = read(); for (i = 1; i <= n; ++ i) for (j = 1; j <= m; ++ j) a[i][j] = read();
for (i = 1; i <= n; ++ i) { l = 1, r = 0, memset(q, 0, sizeof q); L = 1, R = 0, memset(Q, 0, sizeof Q); for (j = 1; j <= m; ++ j) { while (l <= r && q[l] + lim <= j) ++ l; while (l <= r && a[i][q[r]] < a[i][j]) -- r; q[++ r] = j; if (j >= lim) rmax[i][++ rmax[i][0]] = a[i][q[l]];
while (L <= R && Q[L] + lim <= j) ++ L; while (L <= R && a[i][Q[R]] > a[i][j]) -- R; Q[++ R] = j; if (j >= lim) rmin[i][++ rmin[i][0]] = a[i][Q[L]]; } } lin = m - lim + 1, ron = n - lim + 1; for (j = 1; j <= lin; ++ j) { l = 1, r = 0, memset(q, 0, sizeof q); L = 1, R = 0, memset(Q, 0, sizeof Q); for (i = 1; i <= n; ++ i) { while (l <= r && q[l] + lim <= i) ++ l; while (l <= r && rmax[q[r]][j] < rmax[i][j]) -- r; q[++ r] = i; if (i >= lim) cmax[++ cmax[0][j]][j] = rmax[q[l]][j];
while (L <= R && Q[L] + lim <= i) ++ L; while (L <= R && rmin[Q[R]][j] > rmin[i][j]) -- R; Q[++ R] = i; if (i >= lim) cmin[++ cmin[0][j]][j] = rmin[Q[L]][j]; } } for (i = 1; i <= ron; ++ i) for (j = 1; j <= lin; ++ j) res = min(res, cmax[i][j] - cmin[i][j]); put(res);
return 0; }
|