Submission #966590

#	Time	Username	Problem	Language	Result	Execution time	Memory
966590		efedmrlr	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	318 ms	37584 KiB

hyper

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 40;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q;

struct MinST {
    vector<array<int,2> > dt;
    void reset() {
        dt.clear();
    }
    void add_el(int x) {
        if(dt.size()) {
            dt.pb({x, min(x, dt.back()[1])});
        }    
        else {
            dt.pb({x, x});
        }
    }
    int get_min() {
        if(dt.size()) return dt.back()[1];
        return INF;
    }
    void erase() {
        dt.pop_back();
    }
};

struct MinQue {
    MinST st1, st2;
    void reset() {
        st1.reset(); st2.reset();
    }
    void add_el(int x) {
        st1.add_el(x);
    }
    int get_min() {
        return min(st1.get_min(), st2.get_min());
    }
    void erase() {
        if(st2.dt.size()) {
            st2.erase();
            return;
        }
        while(st1.dt.size()) {
            st2.add_el(st1.dt.back()[0]);
            st1.erase();
        }
        if(st2.dt.size()) {
            st2.erase();
        }

    }
};
int a[N][N][N][N];
inline void solve() {
    cin>>n>>m;
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            for(int k = 1; k<=n; k++) {
                for(int l = 1; l<=n; l++) {
                    cin >> a[i][j][k][l];
                }
            }
        }
    }
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            for(int k = 1; k<=n; k++) {
                MinQue st;
                for(int l = 1; l <= m - 1; l++) {
                    st.add_el(a[i][j][k][l]);
                }
                for(int l = m; l<=n; l++) {
                    st.add_el(a[i][j][k][l]);
                    a[i][j][k][l - m + 1] = st.get_min();
                    st.erase();
                }
            }
        }
    }
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            for(int l = 1; l<= n - m + 1; l++){
                MinQue st;
                for(int k = 1; k <= m - 1; k++) {
                    st.add_el(a[i][j][k][l]);
                }
                for(int k = m; k <= n; k++) {
                    st.add_el(a[i][j][k][l]);
                    a[i][j][k - m + 1][l] = st.get_min();
                    st.erase();
                }
            }
        }
    }
    for(int i = 1; i<=n; i++) {
        for(int k = 1; k <= n - m + 1; k++) {
            for(int l = 1; l<= n - m + 1; l++){
                MinQue st;
                for(int j = 1; j <= m - 1; j++) {
                    st.add_el(a[i][j][k][l]);
                }
                for(int j = m; j <= n; j++) {
                    st.add_el(a[i][j][k][l]);
                    a[i][j - m + 1][k][l] = st.get_min();
                    st.erase();
                }
            } 
        }
    }
    for(int j = 1; j<=n - m + 1; j++) {
        for(int k = 1; k <= n - m + 1; k++) {
            for(int l = 1; l<= n - m + 1; l++){
                MinQue st;
                for(int i = 1; i <= m - 1; i++) {
                    st.add_el(a[i][j][k][l]);
                }
                for(int i = m; i <= n; i++) {
                    st.add_el(a[i][j][k][l]);
                    a[i - m + 1][j][k][l] = st.get_min();
                    st.erase();
                }
            } 
        }
    }
    for(int i = 1; i<= n - m + 1; i++) {
        for(int j = 1; j<=n - m + 1; j++) {
            for(int k = 1; k <= n - m + 1; k++) {
                for(int l = 1; l<= n - m + 1; l++) {
                    cout << a[i][j][k][l] << " ";
                }
            }
        }
    }
    cout << "\n";
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

• Subtask 1: 100 / 100