记录编号	571000	评测结果	AAAAAAAAAAAAAAAA
题目名称	[POI 1999] 位图	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2022-05-01 10:52:49	内存使用	2.56 MiB

#include <bits/stdc++.h>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define rep(_x, _y, _z) for (int _x = (_y); _x <= (_z); ++ _x)
#define rep1(_x, _y, _z) for (int _x = (_y); _x < (_z); ++ _x)
#define fi first
#define se second

using i64 = long long;
using PII = std::pair<int, int>;

const int N = 183, INF = 1 << 30;
struct rec { int x, y, z; };
std::vector<rec> a(1);
int c[N * N], tot;
int ans[N][N], n, m, t;

inline int lowbit(int x) { return x & -x; }

int ask(int x) {
	int y = -INF; 
	for (; x; x -= lowbit(x)) y = std::max(y, c[x]);
	return y;
}

void insert(int x, int y) {
	for (; x < tot; x += lowbit(x)) c[x] = std::max(c[x], y);
}

void calc(int st, int ed, int de, int dx, int dy) {
	for (int i = st; i != ed; i += de) {
		int y = (dy == 1) ? a[i].y : tot - a[i].y;
		int tmp = dx * a[i].x + dy * a[i].y;
		if (a[i].z == -1) insert(y, tmp);
		else ans[a[i].x][a[i].y] = std::min(ans[a[i].x][a[i].y], abs(tmp - ask(y))); 
	}
	for (int i = st; i != ed; i += de) {
		int y = (dy == 1) ? a[i].y : tot - a[i].y;
		if (a[i].z == -1) 
			for (int j = y; j < tot; j += lowbit(j)) c[j] = -INF;
	}
}

int main() {
	OPEN(bit);
	scanf("%d%d", &n, &m);
	rep (i, 1, n) rep (j, 1, m) {
		char ch = getchar();
		while (!isdigit(ch)) ch = getchar();
		if (ch == 49) a.emplace_back((rec){i, j, -1});
	}
	rep (i, 1, n) rep(j, 1, m) {
		a.emplace_back((rec){i, j, (int) a.size()});	
	}
	
	tot = m + 1;
	memset(c, 0xcf, sizeof c);
	memset(ans, 0x3f, sizeof ans);

	t = a.size() - 1;
	std::sort(a.begin() + 1, a.end(), [&](rec &_a, rec &_b) {
		return _a.x < _b.x || _a.x == _b.x && _a.y < _b.y;
	});
	calc(1, t + 1, 1, 1, 1), calc(t, 0, -1, -1, -1);
	calc(1, t + 1, 1, 1, -1), calc(t, 0, -1, -1, 1);	
	rep (i, 1, n) {
		rep (j, 1, m) printf("%d ", ans[i][j]);
		puts("");
	}
	return 0;
}