제출 #995168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995168		Sokol080808	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	299 ms	34644 KiB

hyper

#include <bits/stdc++.h>
#include <malloc.h>

using namespace std;

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

struct MinQueue {
    const int INF = 2e9;
    vector<array<int, 2>> st1, st2;

    void add(vector<array<int, 2>>& st, int x) {
        if (st.empty()) {
            st.push_back({x, x});
        } else {
            st.push_back({x, min(st.back()[1], x)});
        }
    }

    void add(int x) {
        add(st2, x);
    }

    void pop() {
        if (st1.empty()) {
            while (!st2.empty()) {
                add(st1, st2.back()[0]);
                st2.pop_back();
            }
        }
        st1.pop_back();
    }

    int res() {
        return min(st1.empty() ? INF : st1.back()[1], st2.empty() ? INF : st2.back()[1]);
    }
    
    void clear() {
        st1.clear();
        st2.clear();
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int a[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 w = 0; w < n; w++) cin >> a[i][j][k][w];

    MinQueue mq;

    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            for (int w = 0; w < n; w++) {
                mq.clear();
                int curi = 0;
                for (int i = 0; i + m - 1 < n; i++) {
                    while (curi < i + m) {
                        mq.add(a[curi][j][k][w]);
                        curi++;
                    }
                    a[i][j][k][w] = mq.res();
                    mq.pop();
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int w = 0; w < n; w++) {
                mq.clear();
                int curj = 0;
                for (int j = 0; j + m - 1 < n; j++) {
                    while (curj < j + m) {
                        mq.add(a[i][curj][k][w]);
                        curj++;
                    }
                    a[i][j][k][w] = mq.res();
                    mq.pop();
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int w = 0; w < n; w++) {
                mq.clear();
                int curk = 0;
                for (int k = 0; k + m - 1 < n; k++) {
                    while (curk < k + m) {
                        mq.add(a[i][j][curk][w]);
                        curk++;
                    }
                    a[i][j][k][w] = mq.res();
                    mq.pop();
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                mq.clear();
                int curw = 0;
                for (int w = 0; w + m - 1 < n; w++) {
                    while (curw < w + m) {
                        mq.add(a[i][j][k][curw]);
                        curw++;
                    }
                    a[i][j][k][w] = mq.res();
                    mq.pop();
                }
            }
        }
    }


    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 w = 0; w < n - m + 1; w++) {
                    cout << a[i][j][k][w] << ' ';
                }
            }
        }
    }

    return 0;
}

• Subtask 1: 100 / 100