답안 #341271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341271	2020-12-29T10:35:30 Z	tranxuanbach	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	410 ms	59500 KB

hyper

#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:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	876 KB	Output is correct
3	Correct	3 ms	1900 KB	Output is correct
4	Correct	3 ms	2412 KB	Output is correct
5	Correct	4 ms	2796 KB	Output is correct
6	Correct	15 ms	5996 KB	Output is correct
7	Correct	11 ms	5100 KB	Output is correct
8	Correct	27 ms	8172 KB	Output is correct
9	Correct	50 ms	14060 KB	Output is correct
10	Correct	29 ms	9324 KB	Output is correct
11	Correct	79 ms	18156 KB	Output is correct
12	Correct	153 ms	28140 KB	Output is correct
13	Correct	127 ms	21868 KB	Output is correct
14	Correct	214 ms	36460 KB	Output is correct
15	Correct	336 ms	51820 KB	Output is correct
16	Correct	179 ms	29932 KB	Output is correct
17	Correct	213 ms	35796 KB	Output is correct
18	Correct	410 ms	59500 KB	Output is correct
19	Correct	277 ms	42988 KB	Output is correct
20	Correct	222 ms	34144 KB	Output is correct