Submission #1141631

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

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

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> (4, 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 {
        for (int i = 0; i < 4; i++)
          tree[cx][cy][i] = min(tree[2 * cx + 1][cy][i], tree[2 * cx + 2][cy][i]);
      }
    } 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 < 4; i++)
        tree[cx][cy][i] = min(tree[cx][2 * cy + 1][i], tree[cx][2 * cy + 2][i]);
    }
  }

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



    // for (int i = 0; i < n; i++)
    //   reverse(a[i].begin(), a[i].begin() + m);

    // reverse(a.begin(), a.begin() + n);

    // segtree st1;
    // st1.build(n, m);

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

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

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