CodeBreaker swimming solution

 avatar
unknown
c_cpp
11 days ago
3.7 kB
3
Indexable
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

vector<vector<int>> mnv[10], mnh[10], mxt[10][10], arr;
int mxg(int x1, int y1, int x2, int y2) {
	if ((y1 > y2) || (x1 > x2)) return -1;
	int lgr = log2(x2 - x1 + 1), lgc = log2(y2 a- y1 + 1);
	int nc = y2 - (1 << lgc) + 1, nr = x2 - (1 << lgr) + 1;
	return max(max(mxt[lgr][lgc][x1][y1], mxt[lgr][lgc][x1][nc]),
		max(mxt[lgr][lgc][nr][y1], mxt[lgr][lgc][nr][nc]));
}

int mnvc(int y, int x1, int x2) {
	if ((x1 > x2)) return 1e9;
	int l = log2(x2 - x1 + 1);
	return min(mnv[l][x1][y],
		mnv[l][x2 - (1 << l) + 1][y]);
}

int mnhc(int x, int y1, int y2) {
	if ((y1 > y2)) return 1e9;
	int l = log2(y2 - y1 + 1);
	return min(mnh[l][x][y1],
		mnh[l][x][y2 - (1 << l) + 1]);
}

int bs(int l, int r, bool rc, int i, int j) {
	int s = l, e = r, ans = -1;
	while (s <= e) {
		int mid = (s + e) / 2;
		if (rc == 0) {
			if (mxg(i, mid, i, j) <= arr[i][j])
				e = mid - 1;
			else s = mid + 1, ans = mid;
		}
		else {
			if (mxg(mid, j, i, j) <= arr[i][j])
				e = mid - 1;
			else s = mid + 1, ans = mid;
		}
	}
	return ans;
}

int bs2(int l, int r, bool rc, int i, int j) {
	int s = l, e = r, ans = -1;
	while (s <= e) {
		int mid = (s + e) / 2;
		if (rc == 0) {
			if (mxg(i, j, i, mid) > arr[i][j])
				e = mid - 1, ans = mid;
			else s = mid + 1;
		}
		else {
			if (mxg(i, j, mid, j) > arr[i][j])
				e = mid - 1, ans = mid;
			else s = mid + 1;
		}
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int r, c; cin >> r >> c;
	arr.resize(r, vector<int>(c));
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> arr[i][j];

	for (int x = 0; x < 10; ++x)
		for (int y = 0; y < 10; ++y) {
			mxt[x][y].resize(r, vector<int>(c));
			for (int i = 0; i < r; ++i)
				for (int j = 0; j < c; ++j) {
					mxt[x][y][i][j] = 0;
					if ((x == 0) && (y == 0))
						mxt[x][y][i][j]
						= arr[i][j];
					else if (x > 0) {
						if ((i + (1 << (x - 1))) < r)
							mxt[x][y][i][j] = max(mxt[x - 1][y][i][j],
								mxt[x - 1][y][i + (1 << (x - 1))][j]);
					}
					else {
						if ((j + (1 << (y - 1))) < c)
							mxt[x][y][i][j] = max(mxt[x][y - 1][i][j],
								mxt[x][y - 1][i][j + (1 << (y - 1))]);
					}
				}
		}

	for (int x = 0; x < 10; ++x) {
		mnh[x].resize(r, vector<int>(c));
		mnv[x].resize(r, vector<int>(c));
		for (int i = 0; i < r; ++i)
			for (int j = 0; j < c; ++j) {
				if (x == 0)
					mnv[x][i][j] = mnh[x][i][j]
					= arr[i][j];
				else {
					if ((i + (1 << (x - 1))) < r)
						mnv[x][i][j] = min(mnv[x - 1][i][j],
							mnv[x - 1][i + (1 << (x - 1))][j]);
					if ((j + (1 << (x - 1))) < c)
						mnh[x][i][j] = min(mnh[x - 1][i][j],
							mnh[x - 1][i][j + (1 << (x - 1))]);
				}
			}
	}

	int ans = 0;
	for (int i = 1; i < (r - 1); ++i)
		for (int j = 1; j < (c - 1); ++j) {
			int um = bs(0, i, 1, i, j);
			int lm = bs(0, j, 0, i, j);
			int dm = bs2(i, r - 1, 1, i, j);
			int rm = bs2(j, c - 1, 0, i, j);
			if ((rm < 0) || (dm < 0) || (um < 0) || (lm < 0))
				continue;

			int ul = max(mxg(um + 1, lm + 1, i, j - 1),
				mxg(um + 1, lm + 1, i - 1, j));
			int ur = mxg(um + 1, j, i, rm - 1);
			int dl = mxg(i, lm + 1, dm - 1, j);
			int dr = mxg(i, j, dm - 1, rm - 1);
			if (ul == arr[i][j]) continue;
			if (max(max(ul, ur), max(dl, dr)) > arr[i][j])
				continue;
			if (mnhc(um, lm + 1, rm - 1) <= arr[i][j])
				continue;
			if (mnhc(dm, lm + 1, rm - 1) <= arr[i][j])
				continue;
			if (mnvc(lm, um + 1, dm - 1) <= arr[i][j])
				continue;
			if (mnvc(rm, um + 1, dm - 1) <= arr[i][j])
				continue;
			++ans;
		}
	cout << ans;
}
Editor is loading...
Leave a Comment