답안 #995168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995168	2024-06-08T14:25:13 Z	Sokol080808	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	299 ms	34644 KB

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

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	452 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	3 ms	596 KB	Output is correct
4	Correct	2 ms	604 KB	Output is correct
5	Correct	2 ms	632 KB	Output is correct
6	Correct	13 ms	1164 KB	Output is correct
7	Correct	8 ms	1164 KB	Output is correct
8	Correct	34 ms	2460 KB	Output is correct
9	Correct	44 ms	4256 KB	Output is correct
10	Correct	24 ms	2648 KB	Output is correct
11	Correct	74 ms	6480 KB	Output is correct
12	Correct	149 ms	12896 KB	Output is correct
13	Correct	122 ms	11812 KB	Output is correct
14	Correct	162 ms	17748 KB	Output is correct
15	Correct	295 ms	28756 KB	Output is correct
16	Correct	171 ms	16980 KB	Output is correct
17	Correct	185 ms	18516 KB	Output is correct
18	Correct	299 ms	34644 KB	Output is correct
19	Correct	263 ms	23568 KB	Output is correct
20	Correct	256 ms	21528 KB	Output is correct