Submission #379731

#	Time	Username	Problem	Language	Result	Execution time	Memory
379731		SolarSystem	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	1899 ms	40724 KiB

hyper

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <math.h>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <stdio.h>
#include <numeric>
#include <iomanip>
#include <random>

using namespace std;

int n, m;

int lg(int k) {
    return 31 - __builtin_clz(k);
}

struct SparseTable2D {
    vector<vector<vector<vector<int>>>> st;

    SparseTable2D () {
        st.resize(n);

        for (int i = 0; i < n; i++) {
            st[i].resize(lg(n) + 1);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= lg(n); j++) {
                st[i][j].resize(n);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= lg(n); j++) {
                for (int k = 0; k < n; k++) {
                    st[i][j][k].resize(lg(n) + 1);
                }
            }
        }
    }

    void build() {
        for (int i = 0; i < n; i++) {
            for (int l = 1; l <= lg(n); l++) {
                for (int k = 0; k + (1 << (l - 1)) < n; k++) {
                    st[i][0][k][l] = min(st[i][0][k][l - 1], st[i][0][k + (1 << (l - 1))][l - 1]);
                }
            }
        }

        for (int j = 1; j <= lg(n); j++) {
            for (int i = 0; i + (1 << (j - 1)) < n; i++) {
                for (int l = 0; l <= lg(n); l++) {
                    for (int k = 0; k < n; k++) {
                        st[i][j][k][l] = min(st[i][j - 1][k][l], st[i + (1 << (j - 1))][j - 1][k][l]);
                    }
                }
            }
        }
    }

    int query(int x1, int y1, int x2, int y2) {
        int kx = lg(x2 - x1 + 1);
        int ky = lg(y2 - y1 + 1);

        int min1 = min(st[x1][kx][y1][ky], st[x1][kx][y2 - (1 << ky) + 1][ky]);
        int min2 = min(st[x2 - (1 << kx) + 1][kx][y1][ky], st[x2 - (1 << kx) + 1][kx][y2 - (1 << ky) + 1][ky]);

        return min(min1, min2);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    int x[n][n][n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    cin >> x[i][j][k][l];
                }
            }
        }
    }

    int z[n][n][n - m + 1][n - m + 1];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            SparseTable2D s;

            for (int k = 0; k < n; k++) {
                for (int l = 0; l < n; l++) {
                    s.st[k][0][l][0] = x[i][j][k][l];
                }
            }

            s.build();

            for (int k = 0; k < n - m + 1; k++) {
                for (int l = 0; l < n - m + 1; l++) {
                    z[i][j][k][l] = s.query(k, l, k + m - 1, l + m - 1);
                }
            }
        }
    }

    int y[n - m + 1][n - m + 1][n - m + 1][n - m + 1];

    for (int k = 0; k < n - m + 1; k++) {
        for (int l = 0; l < n - m + 1; l++) {
            SparseTable2D s;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    s.st[i][0][j][0] = z[i][j][k][l];
                }
            }

            s.build();

            for (int i = 0; i < n - m + 1; i++) {
                for (int j = 0; j < n - m + 1; j++) {
                    y[i][j][k][l] = s.query(i, j, i + m - 1, j + m - 1);
                }
            }
        }
    }

    for (int i = 0; i < n - m + 1; i++) {
        for (int j = 0; j < n - m + 1; j++) {
            for (int k = 0; k < n - m + 1; k++) {
                for (int l = 0; l < n - m + 1; l++) {
                    cout << y[i][j][k][l] << ' ';
                }
            }
        }
    }

    return 0;
}

• Subtask 1: 100 / 100