Submission #1142457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142457		JelalTkm	Maxcomp (info1cup18_maxcomp)	C++17	60 / 100	1098 ms	296036 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 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] = {val - lx - ly, val + lx + ly, val - lx + ly, val + lx - ly};
            } else {
                for (int i = 0; i < 4; i++) {
                    tree[cx][cy][i] = (i % 2 == 0) ? min(tree[2 * cx + 1][cy][i], tree[2 * cx + 2][cy][i]) :
                                                     max(tree[2 * cx + 1][cy][i], tree[2 * cx + 2][cy][i]);
                }
            }
        } 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 < 4; i++) {
                tree[cx][cy][i] = (i % 2 == 0) ? min(tree[cx][2 * cy + 1][i], tree[cx][2 * cy + 2][i]) :
                                                 max(tree[cx][2 * cy + 1][i], tree[cx][2 * cy + 2][i]);
            }
        }
    }

    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;
        auto v = sum_y(cx ,cy * 2 + 1 ,tly ,try_ ,ly ,m);
        auto 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;
        auto v = sum_x(cx * 2 + 1 ,tlx ,trx ,lx ,m ,ly ,ry);
        auto 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() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

          auto v_sum_ij = st.sum(0 ,0,i+1,j+1);
          ans = max(ans,(x-i-j)-v_sum_ij[0]-1);
          ans = max(ans,v_sum_ij[1]-(x+i+j)-1);

          auto v_sum_j_full = st.sum(0,j,i+1,m);
          ans = max(ans,(x-i+j)-v_sum_j_full[2]-1);
          ans = max(ans,v_sum_j_full[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