Submission #683270

#TimeUsernameProblemLanguageResultExecution timeMemory
683270vovamrHyper-minimum (IZhO11_hyper)C++17
100 / 100
317 ms35064 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } constexpr int N = (int)sqrt(sqrt(1500000)) + 2; constexpr int M = 1e5 + 10; int a[N][N][N][N]; int p1 = 0, p2 = 0; pii s1[M], s2[M]; inline void push(int x) { int mn = (!p1 ? x : min(x, s1[p1 - 1].se)); s1[p1++] = {x, mn}; } inline int get_min() { int res = iinf; if (p1) chmin(res, s1[p1 - 1].se); if (p2) chmin(res, s2[p2 - 1].se); return res; } inline void pop() { if (p2) return void(--p2); else { while (p1) { int x = s1[--p1].fi; int mn = (!p2 ? x : min(s2[p2 - 1].se, x)); s2[p2++] = {x, mn}; } --p2; } } inline void clear() { p1 = p2 = 0; } inline void solve() { int n, m; cin >> n >> m; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { for (int z = 0; z < n; ++z) { cin >> a[i][j][k][z]; }}}} for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { clear(); for (int p = 0; p < m; ++p) push(a[i][j][k][p]); for (int p = 0; p + m - 1 < n; ++p) { a[i][j][k][p] = get_min(); pop(); if (p + m < n) push(a[i][j][k][p + m]); } }}} for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int z = 0; z + m - 1 < n; ++z) { clear(); for (int p = 0; p < m; ++p) push(a[i][j][p][z]); for (int p = 0; p + m - 1 < n; ++p) { a[i][j][p][z] = get_min(); pop(); if (p + m - 1 < n) push(a[i][j][p + m][z]); } }}} for (int i = 0; i < n; ++i) { for (int k = 0; k + m - 1 < n; ++k) { for (int z = 0; z + m - 1 < n; ++z) { clear(); for (int p = 0; p < m; ++p) push(a[i][p][k][z]); for (int p = 0; p + m - 1 < n; ++p) { a[i][p][k][z] = get_min(); pop(); if (p + m < n) push(a[i][p + m][k][z]); } }}} for (int j = 0; j + m - 1 < n; ++j) { for (int k = 0; k + m - 1 < n; ++k) { for (int z = 0; z + m - 1 < n; ++z) { clear(); for (int p = 0; p < m; ++p) push(a[p][j][k][z]); for (int p = 0; p + m - 1 < n; ++p) { a[p][j][k][z] = get_min(); pop(); if (p + m < n) push(a[p + m][j][k][z]); } }}} for (int i = 0; i + m - 1 < n; ++i) { for (int j = 0; j + m - 1 < n; ++j) { for (int k = 0; k + m - 1 < n; ++k) { for (int z = 0; z + m - 1 < n; ++z) { cout << a[i][j][k][z] << " "; }}}} } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...