제출 #1014487

#제출 시각아이디문제언어결과실행 시간메모리
1014487LOLOLOHyper-minimum (IZhO11_hyper)C++17
100 / 100
250 ms37200 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 100;
int X[41][41][41][41];

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

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

    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            for (int c = 1; c <= n; c++) {
                for (int d = 1; d <= n; d++)
                    cin >> X[a][b][c][d];
            }
        }
    }

    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            for (int c = 1; c <= n; c++) {
                deque <pair <int, int>> dq;
                for (int d = n; d >= 1; d--) {
                    while (sz(dq) && dq.back().f >= X[a][b][c][d])
                        dq.pop_back();

                    dq.pb({X[a][b][c][d], d});
                    if (d <= n - m + 1) {
                        while (dq.front().s >= d + m)
                            dq.pop_front();

                        X[a][b][c][d] = dq.front().f;
                    }
                }
            }
        }
    }

    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            for (int d = 1; d <= n; d++) {
                deque <pair <int, int>> dq;
                for (int c = n; c >= 1; c--) {
                    while (sz(dq) && dq.back().f >= X[a][b][c][d])
                        dq.pop_back();

                    dq.pb({X[a][b][c][d], c});
                    if (c <= n - m + 1) {
                        while (dq.front().s >= c + m)
                            dq.pop_front();

                        X[a][b][c][d] = dq.front().f;
                    }
                }
            }
        }
    }

    for (int a = 1; a <= n; a++) {
        for (int c = 1; c <= n; c++) {
            for (int d = 1; d <= n; d++) {
                deque <pair <int, int>> dq;
                for (int b = n; b >= 1; b--) {
                    while (sz(dq) && dq.back().f >= X[a][b][c][d])
                        dq.pop_back();

                    dq.pb({X[a][b][c][d], b});
                    if (b <= n - m + 1) {
                        while (dq.front().s >= b + m)
                            dq.pop_front();

                        X[a][b][c][d] = dq.front().f;
                    }
                }
            }
        }
    }


    for (int b = 1; b <= n; b++) {
        for (int c = 1; c <= n; c++) {
            for (int d = 1; d <= n; d++) {
                deque <pair <int, int>> dq;
                for (int a = n; a >= 1; a--) {
                    while (sz(dq) && dq.back().f >= X[a][b][c][d])
                        dq.pop_back();

                    dq.pb({X[a][b][c][d], a});
                    if (a <= n - m + 1) {
                        while (dq.front().s >= a + m)
                            dq.pop_front();

                        X[a][b][c][d] = dq.front().f;
                    }
                }
            }
        }
    }

    for (int a = 1; a + m - 1 <= n; a++) {
        for (int b = 1; b + m - 1 <= n; b++) {
            for (int c = 1; c + m - 1 <= n; c++) {
                for (int d = 1; d + m - 1 <= n; d++) {
                    cout << X[a][b][c][d] << " ";
                }
            }
        }
    }
    return 0;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...