Submission #333659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
333659	2020-12-07T10:34:42 Z	apostoldaniel854	Hyper-minimum (IZhO11_hyper)	C++14	100 / 100	515 ms	44396 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	3 ms	620 KB	Output is correct
5	Correct	4 ms	768 KB	Output is correct
6	Correct	13 ms	1772 KB	Output is correct
7	Correct	11 ms	1644 KB	Output is correct
8	Correct	27 ms	3860 KB	Output is correct
9	Correct	63 ms	5612 KB	Output is correct
10	Correct	29 ms	3948 KB	Output is correct
11	Correct	101 ms	9332 KB	Output is correct
12	Correct	180 ms	18796 KB	Output is correct
13	Correct	128 ms	17644 KB	Output is correct
14	Correct	246 ms	23488 KB	Output is correct
15	Correct	409 ms	36044 KB	Output is correct
16	Correct	199 ms	24464 KB	Output is correct
17	Correct	237 ms	25808 KB	Output is correct
18	Correct	515 ms	44396 KB	Output is correct
19	Correct	309 ms	33364 KB	Output is correct
20	Correct	235 ms	31212 KB	Output is correct