Submission #1142455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142455		JelalTkm	Maxcomp (info1cup18_maxcomp)	C++20	60 / 100	1108 ms	296120 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 md = 1e9 + 7;
const int INF = 1e9 + 5000;

int n, m;

struct segtree {
 
  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<int>> (2 * size_m, vector<int> {INF, -INF, 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] = a[lx][ly] - lx - ly;
  //         tree[cx][cy][1] = a[lx][ly] + lx + ly;
  //         tree[cx][cy][2] = a[lx][ly] - lx + ly;
  //         tree[cx][cy][3] = a[lx][ly] + lx - ly;
  //       }
  //     }
  //     else {
  //       tree[cx][cy][0] = min(tree[2 * cx + 1][cy][0], tree[2 * cx + 2][cy][0]);
  //       tree[cx][cy][1] = max(tree[2 * cx + 1][cy][1], tree[2 * cx + 2][cy][1]);
  //       tree[cx][cy][2] = min(tree[2 * cx + 1][cy][2], tree[2 * cx + 2][cy][2]);
  //       tree[cx][cy][3] = max(tree[2 * cx + 1][cy][3], tree[2 * cx + 2][cy][3]);
  //     }
  //   } 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);
  //     tree[cx][cy][0] = min(tree[cx][2 * cy + 1][0], tree[cx][2 * cy + 2][0]);
  //     tree[cx][cy][1] = max(tree[cx][2 * cy + 1][1], tree[cx][2 * cy + 2][1]);
  //     tree[cx][cy][2] = min(tree[cx][2 * cy + 1][2], tree[cx][2 * cy + 2][2]);
  //     tree[cx][cy][3] = max(tree[cx][2 * cy + 1][3], tree[cx][2 * cy + 2][3]);
  //   }
  // }

  // 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);
  // }

  void update_y(int cx, int lx, int rx, int cy, int ly, int ry, int x, int y, int val) {
    if (ry - ly == 1) {
      if (rx - lx == 1) {
          tree[cx][cy][0] = val - lx - ly;
          tree[cx][cy][1] = val + lx + ly;
          tree[cx][cy][2] = val - lx + ly;
          tree[cx][cy][3] = val + lx - ly;
      }
      else {
        tree[cx][cy][0] = min(tree[2 * cx + 1][cy][0], tree[2 * cx + 2][cy][0]);
        tree[cx][cy][1] = max(tree[2 * cx + 1][cy][1], tree[2 * cx + 2][cy][1]);
        tree[cx][cy][2] = min(tree[2 * cx + 1][cy][2], tree[2 * cx + 2][cy][2]);
        tree[cx][cy][3] = max(tree[2 * cx + 1][cy][3], tree[2 * cx + 2][cy][3]);
      }
    }
    else {
      int m = (ly + ry) >> 1;
      if (y < m)
        update_y(cx, lx, rx, 2 * cy + 1, ly, m, x, y, val);
      else
        update_y(cx, lx, rx, 2 * cy + 2, m, ry, x, y, val);
      tree[cx][cy][0] = min(tree[cx][2 * cy + 1][0], tree[cx][2 * cy + 2][0]);
      tree[cx][cy][1] = max(tree[cx][2 * cy + 1][1], tree[cx][2 * cy + 2][1]);
      tree[cx][cy][2] = min(tree[cx][2 * cy + 1][2], tree[cx][2 * cy + 2][2]);
      tree[cx][cy][3] = max(tree[cx][2 * cy + 1][3], tree[cx][2 * cy + 2][3]);
    }
  }
   
  void update_x (int cx, int lx, int rx, int x, int y, int val) {
    if (rx - lx == 1) {
      update_y(cx, lx, rx, 0, 0, size_m, x, y, val);
    } else {
      int m = (lx + rx) >> 1;
      if (x < m)
        update_x (cx * 2 + 1, lx, m, x, y, val);
      else
        update_x (cx * 2 + 2, m, rx, x, y, val);
      update_y(cx, lx, rx, 0, 0, size_m, x, y, val);
    }
  }

  void update(int x, int y, int val) {
    update_x(0, 0, size_n, x, y, val);
    return;
  }

  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];
    }
    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;
    segtree st;
    st.init(n, m);
    int ans = -1;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) {
        int x;
        cin >> x;
        st.update(i, j, x);
        if (true) {
          vector<int> v = st.sum(0, 0, i + 1, j + 1);
          ans = max(ans, (x - i - j) - v[0] - 1);
          ans = max(ans, v[1] - (x + i + j) - 1);
        }
        if (true) {
          vector<int> v = st.sum(0, j, i + 1, m);
          ans = max(ans, (x - i + j) - v[2] - 1);
          ans = max(ans, v[3] - (x + i - j) - 1);
        }
      }

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

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