답안 #1014487

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014487	2024-07-05T03:52:07 Z	LOLOLO	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	250 ms	37200 KB

hyper

#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;
} 

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2392 KB	Output is correct
3	Correct	2 ms	4444 KB	Output is correct
4	Correct	2 ms	4572 KB	Output is correct
5	Correct	2 ms	2648 KB	Output is correct
6	Correct	8 ms	5188 KB	Output is correct
7	Correct	9 ms	3676 KB	Output is correct
8	Correct	21 ms	5576 KB	Output is correct
9	Correct	29 ms	7252 KB	Output is correct
10	Correct	22 ms	5824 KB	Output is correct
11	Correct	55 ms	10716 KB	Output is correct
12	Correct	120 ms	16844 KB	Output is correct
13	Correct	108 ms	15812 KB	Output is correct
14	Correct	150 ms	20988 KB	Output is correct
15	Correct	215 ms	31824 KB	Output is correct
16	Correct	159 ms	20420 KB	Output is correct
17	Correct	173 ms	21652 KB	Output is correct
18	Correct	250 ms	37200 KB	Output is correct
19	Correct	216 ms	26448 KB	Output is correct
20	Correct	178 ms	24144 KB	Output is correct