제출 #333659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333659		apostoldaniel854	최솟값 배열 (IZhO11_hyper)	C++14	100 / 100	515 ms	44396 KiB

hyper

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"

struct MinDeque {
    deque <pair <int, int>> dq;
    inline void add (int val, int index) {
        while (dq.size () && dq.back ().first >= val)
            dq.pop_back ();
        dq.push_back ({val, index});
    }
    inline int extract (int bound) {
        while (dq.size () && dq.front ().second < bound)
            dq.pop_front ();
        return dq.front ().first;
    }
};
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, m;
    cin >> n >> m;
    vector <vector <vector <vector <int>>>> X, Y;
    X.resize (n + 1);
    for (int i = 1; i <= n; i++) {
        X[i].resize (n + 1);
        for (int j = 1; j <= n; j++) {
            X[i][j].resize (n + 1);
            for (int k = 1; k <= n; k++) {
                X[i][j][k].resize (n + 1);
                for (int l = 1; l <= n; l++) {
                    cin >> X[i][j][k][l];
                }
            }
        }
    }
    Y = X;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                MinDeque dq;
                for (int l = 1; l <= n; l++)  {
                    dq.add (Y[i][j][k][l], l);
                    if (l >= m)
                        Y[i][j][k][l - m + 1] = dq.extract (l - m + 1);
                }
            }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int l = 1; l <= n - m + 1; l++) {
                MinDeque dq;
                for (int k = 1; k <= n; k++) {
                    dq.add (Y[i][j][k][l], k);
                    if (k >= m)
                        Y[i][j][k - m + 1][l] = dq.extract (k - m + 1);
                }
            }
    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++) {
                MinDeque dq;
                for (int j = 1; j <= n; j++) {
                    dq.add (Y[i][j][k][l], j);
                    if (j >= m)
                        Y[i][j - m + 1][k][l] = dq.extract (j - m + 1);
                }
            }

    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++) {
                MinDeque dq;
                for (int i = 1; i <= n; i++) {
                    dq.add (Y[i][j][k][l], i);
                    if (i >= m)
                        Y[i - m + 1][j][k][l] = dq.extract (i - m + 1);
                }
            }
    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 << Y[i][j][k][l] << " ";
    cout << "\n";
    return 0;
}

• Subtask 1: 100 / 100