제출 #1290656

#제출 시각아이디문제언어결과실행 시간메모리
1290656MinhKien최솟값 배열 (IZhO11_hyper)C++20
100 / 100
309 ms52204 KiB
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n, m;
vector < vector < vector < vector <int> > > > v, one, two, three, four;
deque <int> q;

void Resize(vector < vector < vector < vector <int> > > > &k) {
    k.resize(n);
    for (int i = 0; i < n; ++i) {
        k[i].resize(n);
        for (int j = 0; j < n; ++j) {
            k[i][j].resize(n);
            for (int x = 0; x < n; ++x) {
                k[i][j][x].resize(n);
            }
        }
    }
}

void Clear() {
    while (!q.empty()) q.pop_back();
}

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

    cin >> n >> m;

    Resize(v);
    Resize(one);
    Resize(two);
    Resize(three);
    Resize(four);

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

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

                Clear();
                for (int y = n - 1; y >= 0; --y) {
                    while (!q.empty() && v[i][j][x][q.back()] >= v[i][j][x][y]) q.pop_back();
                    while (!q.empty() && y + m - 1 < q.front()) q.pop_front();
                    q.push_back(y);
                    if (y <= n - m) one[i][j][x][y] = v[i][j][x][q.front()];
                }

            }
        }
    }

    for (int y = 0; y <= n - m; ++y) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {

                Clear();
                for (int x = n - 1; x >= 0; --x) {
                    while (!q.empty() && one[i][j][q.back()][y] >= one[i][j][x][y]) q.pop_back();
                    while (!q.empty() && x + m - 1 < q.front()) q.pop_front();
                    q.push_back(x);
                    if (x <= n - m) two[i][j][x][y] = one[i][j][q.front()][y];
                }

            }
        }
    }

    for (int x = 0; x <= n - m; ++x) {
        for (int y = 0; y <= n - m; ++y) {
            for (int i = 0; i < n; ++i) {

                Clear();
                for (int j = n - 1; j >= 0; --j) {
                    while (!q.empty() && two[i][q.back()][x][y] >= two[i][j][x][y]) q.pop_back();
                    while (!q.empty() && j + m - 1 < q.front()) q.pop_front();
                    q.push_back(j);
                    if (j <= n - m) three[i][j][x][y] = two[i][q.front()][x][y];
                }

            }
        }
    }

    for (int j = 0; j <= n - m; ++j) {
        for (int x = 0; x <= n - m; ++x) {
            for (int y = 0; y <= n - m; ++y) {

                Clear();
                for (int i = n - 1; i >= 0; --i) {
                    while (!q.empty() && three[q.back()][j][x][y] >= three[i][j][x][y]) q.pop_back();
                    while (!q.empty() && i + m - 1 < q.front()) q.pop_front();
                    q.push_back(i);
                    if (i <= n - m) four[i][j][x][y] = three[q.front()][j][x][y];
                }

            }
        }
    }

    for (int i = 0; i <= n - m; ++i) {
        for (int j = 0; j <= n - m; ++j) {
            for (int x = 0; x <= n - m; ++x) {
                for (int y = 0; y <= n - m; ++y) {

                    cout << four[i][j][x][y] << " ";

                }
            }
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...