제출 #1142505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142505		JelalTkm	Maxcomp (info1cup18_maxcomp)	C++17	60 / 100	383 ms	589824 KiB

maxcomp

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using namespace std;

#define int long long int

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

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

struct segtree {
 
  vector<vector<vector<vector<int>>>> tree;
  vector<vector<vector<vector<bool>>>> ok;
  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> {0, 0})));
    ok.assign(2 * size_n, vector<vector<vector<bool>>> (2 * size_m, vector<vector<bool>> (2, vector<bool> {false, false})));
  }
 
  // 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);
  // }

  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][0] = val - lx - ly;
          tree[cx][cy][1][0] = val - lx + ly;
          tree[cx][cy][0][1] = val + lx + ly;
          tree[cx][cy][1][1] = val + lx - ly;
          ok[cx][cy][0][0] = true;
          ok[cx][cy][0][1] = true;
          ok[cx][cy][1][0] = true;
          ok[cx][cy][1][1] = true;
          // cout << lx + 1 << " " << rx << "   " << ly + 1 << " " << ry << '\n';
          // cout << tree[cx][cy][1][0] << '\n';
          // cout << '\n';
      }
      else {
        for (int i = 0; i < 2; i++) {
          int v = (ok[2 * cx + 1][cy][i][0] ? tree[2 * cx + 1][cy][i][0] : INF);
          int v1 = (ok[2 * cx + 2][cy][i][0] ? tree[2 * cx + 2][cy][i][0] : INF);
          tree[cx][cy][i][0] = min(v, v1);

          v = (ok[2 * cx + 1][cy][i][1] ? tree[2 * cx + 1][cy][i][1] : -INF);
          v1 = (ok[2 * cx + 2][cy][i][1] ? tree[2 * cx + 2][cy][i][1] : -INF);
          tree[cx][cy][i][1] = max(v, v1);
        }
        ok[cx][cy][0][0] = true;
        ok[cx][cy][0][1] = true;
        ok[cx][cy][1][0] = true;
        ok[cx][cy][1][1] = true;
        // cout << lx + 1 << " " << rx << "   " << ly + 1 << " " << ry << '\n';
        // cout << tree[cx][cy][1][0] << '\n';
        // cout << '\n';
      }
    }
    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);
      for (int i = 0; i < 2; i++) {
        int v = (ok[cx][2 * cy + 1][i][0] ? tree[cx][2 * cy + 1][i][0] : INF);
        int v1 = (ok[cx][2 * cy + 2][i][0] ? tree[cx][2 * cy + 2][i][0] : INF);
        // cout << cx << " " << 2 * cy + 1 << '\n';
        tree[cx][cy][i][0] = min(v, v1);
        
        v = (ok[cx][2 * cy + 1][i][1] ? tree[cx][2 * cy + 1][i][1] : -INF);
        v1 = (ok[cx][2 * cy + 2][i][1] ? tree[cx][2 * cy + 2][i][1] : -INF);
        tree[cx][cy][i][1] = max(v, v1);
      }
      ok[cx][cy][0][0] = true;
      ok[cx][cy][0][1] = true;
      ok[cx][cy][1][0] = true;
      ok[cx][cy][1][1] = true;
      // cout << lx + 1 << " " << rx << "   " << ly + 1 << " " << ry << '\n';
      // cout << tree[cx][cy][1][0] << '\n';
      // cout << '\n';
    }
  }
   
  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_) {
      if (ok[cx][cy][0][0])
        return {tree[cx][cy][0][0], tree[cx][cy][0][1], tree[cx][cy][1][0], tree[cx][cy][1][1]};
      else return {INF, -INF, INF, -INF};
    }
    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;
        // cout << i + j + 1 << '\n';
        st.update(i, j, x);
        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);
        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