oj.uz

답안 #683365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683365 2023-01-18T09:07:33 Z nifeshe 최솟값 배열 (IZhO11_hyper) C++14
100 / 100
 348 ms 42136 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (x).size()
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 35 + 2;
const int lg = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

vector<int> govno(vector<int> a, int m) {
    int n = sz(a);
    deque<int> q;
    vector<int> ans(n - m + 1);
    for(int i = 0; i < n; i++) {
        while(sz(q)) {
            if(a[q.back()] >= a[i]) q.pop_back();
            else break;
        }
        q.pb(i);
        if(i >= m - 1) {
            ans[i - m + 1] = a[q.front()];
            if(q.front() == i - m + 1) q.pop_front();
        }
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<vector<vector<int>>>> a(n, vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(n))));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                for(int l = 0; l < n; l++) {
                    cin >> a[i][j][k][l];
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                auto curr = govno(a[i][j][k], m);
                for(int l = 0; l < n - m + 1; l++) a[i][j][k][l] = curr[l];
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n - m + 1; k++) {
                vector<int> hate(n);
                for(int l = 0; l < n; l++) hate[l] = a[i][j][l][k];
                auto curr = govno(hate, m);
                for(int l = 0; l < n - m + 1; l++) a[i][j][l][k] = curr[l];
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n - m + 1; j++) {
            for(int k = 0; k < n - m + 1; k++) {
                vector<int> hate(n);
                for(int l = 0; l < n; l++) hate[l] = a[i][l][j][k];
                auto curr = govno(hate, m);
                for(int l = 0; l < n - m + 1; l++) a[i][l][j][k] = curr[l];
            }
        }
    }
    for(int i = 0; i < n - m + 1; i++) {
        for(int j = 0; j < n - m + 1; j++) {
            for(int k = 0; k < n - m + 1; k++) {
                vector<int> hate(n);
                for(int l = 0; l < n; l++) hate[l] = a[l][i][j][k];
                auto curr = govno(hate, m);
                for(int l = 0; l < n - m + 1; l++) a[l][i][j][k] = curr[l];
            }
        }
    }
    for(int i = 0; i < n - m + 1; i++) {
        for(int j = 0; j < n - m + 1; j++) {
            for(int k = 0; k < n - m + 1; k++) {
                for(int l = 0; l < n - m + 1; l++) {
                    cout << a[i][j][k][l] << " ";
                }
            }
        }
    }
}

signed main() {
    //freopen("hyper.in", "r", stdin); freopen("hyper.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message

hyper.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 10 ms 1492 KB Output is correct
7 Correct 9 ms 1380 KB Output is correct
8 Correct 21 ms 3544 KB Output is correct
9 Correct 42 ms 5292 KB Output is correct
10 Correct 24 ms 3636 KB Output is correct
11 Correct 63 ms 8616 KB Output is correct
12 Correct 132 ms 17356 KB Output is correct
13 Correct 127 ms 16184 KB Output is correct
14 Correct 186 ms 22068 KB Output is correct
15 Correct 324 ms 34680 KB Output is correct
16 Correct 148 ms 23164 KB Output is correct
17 Correct 180 ms 24508 KB Output is correct
18 Correct 348 ms 42136 KB Output is correct
19 Correct 251 ms 31168 KB Output is correct
20 Correct 201 ms 29040 KB Output is correct