题解:AT_bogosortcontest_div1_c Moving Silver
stripe_python · · 题解
设
边界
令
:::::success[断言的证明]{open}
任取阈值
引理 若
证明 设
所以让
若
必有
而
将引理应用在
令
:::::
只要做
将询问离线后滚动数组,时间
const int N = 605, M = 2e5 + 5, inf = 2e9;
const int dirx[] = {-1, -1, -1, +1, +1};
const int diry[] = {-1, 0, +1, -1, +1};
int n, m, k, q, a[N][N], ans[M];
int f[2][N][N], g[2][N][N];
vector<tuple<int, int, int>> Q[N];
void _main() {
cin >> n >> m; k = n/2+1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
f[0][i][j] = g[0][i][j] = a[i][j];
}
cin >> q;
for (i64 i = 1, x, y, c; i <= q; i++) {
cin >> x >> y >> c;
c = min(c, 2*k+c%2);
Q[c].pb(x, y, i);
}
for (int i = 1, st = 1; i <= 2*k+1; i++, st^=1) {
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++) {
f[st][x][y] = -inf, g[st][x][y] = inf;
for (int d = 0; d < 5; d++) {
int nx = x + dirx[d], ny = y + diry[d];
if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
chkmax(f[st][x][y], g[st^1][nx][ny]);
chkmin(g[st][x][y], f[st^1][nx][ny]);
}
}
for (auto [x, y, id] : Q[i]) ans[id] = f[st][x][y];
}
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}