Submission #379731

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
379731	2021-03-19T06:13:30 Z	SolarSystem	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	1899 ms	40724 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	4 ms	492 KB	Output is correct
4	Correct	5 ms	492 KB	Output is correct
5	Correct	6 ms	620 KB	Output is correct
6	Correct	28 ms	1388 KB	Output is correct
7	Correct	22 ms	1388 KB	Output is correct
8	Correct	70 ms	2668 KB	Output is correct
9	Correct	143 ms	5612 KB	Output is correct
10	Correct	77 ms	2904 KB	Output is correct
11	Correct	279 ms	7788 KB	Output is correct
12	Correct	578 ms	11788 KB	Output is correct
13	Correct	442 ms	9068 KB	Output is correct
14	Correct	787 ms	19580 KB	Output is correct
15	Correct	1539 ms	30624 KB	Output is correct
16	Correct	811 ms	10880 KB	Output is correct
17	Correct	994 ms	14084 KB	Output is correct
18	Correct	1899 ms	40724 KB	Output is correct
19	Correct	1320 ms	26164 KB	Output is correct
20	Correct	1008 ms	22348 KB	Output is correct