Submission #341271

#TimeUsernameProblemLanguageResultExecution timeMemory
341271tranxuanbachHyper-minimum (IZhO11_hyper)C++17
100 / 100
410 ms59500 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef vector <pii> vpii;
typedef vector <vi> vvi;

const int N = 36;

int n, m;
int a[N][N][N][N], b[N][N][N][N], c[N][N][N][N], d[N][N][N][N], e[N][N][N][N];

deque <pii> dq;

void reset(){
    dq.clear();
}

void add(int pos, int val){
    while (!dq.empty() && dq.back().se >= val){
        dq.pop_back();
    }
    dq.push_back(make_pair(pos, val));
}

void del(int pos){
    if (!dq.empty() && dq.front().fi == pos){
        dq.pop_front();
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ForE(i, 1, n){
        ForE(j, 1, n){
            ForE(k, 1, n){
                ForE(l, 1, n){
                    cin >> a[i][j][k][l];
                }
            }
        }
    }
    ForE(i, 1, n){
        ForE(j, 1, n){
            ForE(k, 1, n){
                reset();
                ForE(l, 1, n){
                    add(l, a[i][j][k][l]);
                    if (l >= m){
                        b[i][j][k][l] = dq.front().se;
                        del(l - m + 1);
                    }
                }
            }
        }
    }
    ForE(i, 1, n){
        ForE(j, 1, n){
            ForE(l, m, n){
                reset();
                ForE(k, 1, n){
                    add(k, b[i][j][k][l]);
                    if (k >= m){
                        c[i][j][k][l] = dq.front().se;
                        del(k - m + 1);
                    }
                }
            }
        }
    }
    ForE(i, 1, n){
        ForE(k, m, n){
            ForE(l, m, n){
                reset();
                ForE(j, 1, n){
                    add(j, c[i][j][k][l]);
                    if (j >= m){
                        d[i][j][k][l] = dq.front().se;
                        del(j - m + 1);
                    }
                }
            }
        }
    }
    ForE(j, m, n){
        ForE(k, m, n){
            ForE(l, m, n){
                reset();
                ForE(i, 1, n){
                    add(i, d[i][j][k][l]);
                    if (i >= m){
                        e[i][j][k][l] = dq.front().se;
                        del(i - m + 1);
                    }
                }
            }
        }
    }
    ForE(i, m, n){
        ForE(j, m, n){
            ForE(k, m, n){
                ForE(l, m, n){
                    cout << e[i][j][k][l] << ' ';
                }
            }
        }
    }
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/
#Verdict Execution timeMemoryGrader output
Fetching results...