CodeBreaker swimming solution
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