Submission #966590

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
966590	2024-04-20T05:49:44 Z	efedmrlr	Hyper-minimum (IZhO11_hyper)	C++17	100 / 100	318 ms	37584 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	3 ms	4444 KB	Output is correct
4	Correct	2 ms	4440 KB	Output is correct
5	Correct	3 ms	4696 KB	Output is correct
6	Correct	9 ms	5208 KB	Output is correct
7	Correct	9 ms	4956 KB	Output is correct
8	Correct	18 ms	8004 KB	Output is correct
9	Correct	38 ms	9808 KB	Output is correct
10	Correct	21 ms	8284 KB	Output is correct
11	Correct	54 ms	13136 KB	Output is correct
12	Correct	107 ms	17848 KB	Output is correct
13	Correct	95 ms	16724 KB	Output is correct
14	Correct	172 ms	22552 KB	Output is correct
15	Correct	285 ms	32284 KB	Output is correct
16	Correct	129 ms	20676 KB	Output is correct
17	Correct	156 ms	22364 KB	Output is correct
18	Correct	318 ms	37584 KB	Output is correct
19	Correct	201 ms	26800 KB	Output is correct
20	Correct	154 ms	24508 KB	Output is correct