Submission #1142449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142449		JelalTkm	Maxcomp (info1cup18_maxcomp)	C++20	60 / 100	505 ms	589824 KiB

maxcomp

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

#define int long long int

const int N = 1e3 + 1;
const int INF = 1e9 + 5e3;
const int md = 1e9 + 7;

int n, m;
vector<vector<int>> a(N, vector<int> (N));

struct segtree {
 
  vector<vector<vector<vector<int>>>> tree;
  int size_n, size_m;

  void init(int n, int m) {
    size_n = 1, size_m = 1;
    while (size_n < n) size_n <<= 1;
    while (size_m < m) size_m <<= 1;
    tree.assign(2 * size_n, vector<vector<vector<int>>> (2 * size_m, vector<vector<int>> (2, vector<int> {INF, -INF})));
  }
 
  void build_y(int cx, int lx, int rx, int cy, int ly, int ry) {
    if (ry - ly == 1) {
      if (rx - lx == 1) {
        if (lx < n && ly < m) {
          tree[cx][cy][0][0] = a[lx][ly] - lx - ly;
          tree[cx][cy][1][0] = a[lx][ly] - lx + ly;
          tree[cx][cy][0][1] = a[lx][ly] + lx + ly;
          tree[cx][cy][1][1] = a[lx][ly] + lx - ly;
        }
      }
      else {
        for (int i = 0; i < 2; i++) {
          tree[cx][cy][i][0] = min(tree[2 * cx + 1][cy][i][0], tree[2 * cx + 2][cy][i][0]);
          tree[cx][cy][i][1] = max(tree[2 * cx + 1][cy][i][1], tree[2 * cx + 2][cy][i][1]);
        }
      }
    } else {
      int m = (ly + ry) >> 1;
      build_y(cx, lx, rx, 2 * cy + 1, ly, m);
      build_y(cx, lx, rx, 2 * cy + 2, m, ry);
      for (int i = 0; i < 2; i++) {
        tree[cx][cy][i][0] = min(tree[cx][2 * cy + 1][i][0], tree[cx][2 * cy + 2][i][0]);
        tree[cx][cy][i][1] = max(tree[cx][2 * cy + 1][i][1], tree[cx][2 * cy + 2][i][1]);
      }
    }
  }

  void build_x(int cx, int lx, int rx) {
    if (rx - lx == 1) {
      build_y(cx, lx, rx, 0, 0, size_m);
      return;
    }
    int m = (lx + rx) >> 1;
    build_x(2 * cx + 1, lx, m);
    build_x(2 * cx + 2, m, rx);
    build_y(cx, lx, rx, 0, 0, size_m);
  }

  void build(int n, int m) {
    init(n, m);
    build_x(0, 0, size_n);
  }

  vector<int> sum_y(int cx, int cy, int tly, int try_, int ly, int ry) {
    if (tly >= ry || ly >= try_) {
      return {INF, -INF, INF, -INF};
    }
    if (ly >= tly && ry <= try_) {
      return {tree[cx][cy][0][0], tree[cx][cy][0][1], tree[cx][cy][1][0], tree[cx][cy][1][1]};
    }
    int m = (ly + ry) >> 1;
    vector<int> v = sum_y (cx, cy * 2 + 1, tly, try_, ly, m);
    vector<int> v1 = sum_y (cx, cy * 2 + 2, tly, try_, m, ry);
    return {min(v[0], v1[0]), max(v[1], v1[1]), min(v[2], v1[2]), max(v[3], v1[3])};
  }

  vector<int> sum_x(int cx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (tlx >= rx || lx >= trx) {
      return {INF, -INF, INF, -INF};
    }
    if (lx >= tlx && rx <= trx) {
      return sum_y(cx, 0, ly, ry, 0, size_m);
    }
    int m = (lx + rx) >> 1;
    vector<int> v = sum_x (cx * 2 + 1, tlx, trx, lx, m, ly, ry);
    vector<int> v1 = sum_x (cx * 2 + 2, tlx, trx, m, rx, ly, ry);
    return {min(v[0], v1[0]), max(v[1], v1[1]), min(v[2], v1[2]), max(v[3], v1[3])};
  }

  vector<int> sum(int x1, int y1, int x2, int y2) {
    return sum_x(0, x1, x2, 0, size_n, y1, y2);
  }

};

int32_t main(int32_t argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T = 1;
  // cin >> T;
  while (T--) {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        cin >> a[i][j];

    segtree st;
    st.build(n, m);

    int ans = -1;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (true) {
          vector<int> v = st.sum(0, 0, i + 1, j + 1);
          ans = max(ans, (a[i][j] - i - j) - v[0] - 1);
          ans = max(ans, v[1] - (a[i][j] + i + j) - 1);
        }
        if (true) {
          vector<int> v = st.sum(0, j, i + 1, m);
          ans = max(ans, (a[i][j] - i + j) - v[2] - 1);
          ans = max(ans, v[3] - (a[i][j] + i - j) - 1);
        }
      }
    }

    cout << ans << '\n';
  }
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40