Submission #58117

#TimeUsernameProblemLanguageResultExecution timeMemory
58117BenqHyper-minimum (IZhO11_hyper)C++14
0 / 100
514 ms92636 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; int N,M, X[34][34][34][34]; void solve(int d) { if (d == 3) { F0R(i,N) F0R(j,N) F0R(k,N) { deque<pi> d; F0Rd(l,N) { while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back(); d.pb({X[i][j][k][l],l}); if (l <= N-M) { while (d.front().s >= l+M) d.pop_front(); X[i][j][k][l] = d.front().f; } } } } else if (d == 2) { F0R(i,N) F0R(j,N) F0R(l,N-M+1) { deque<pi> d; F0Rd(k,N) { while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back(); d.pb({X[i][j][k][l],k}); if (k <= N-M) { while (d.front().s >= k+M) d.pop_front(); X[i][j][k][l] = d.front().f; } } } } else if (d == 1) { F0R(i,N) F0R(k,N-M+1) F0R(l,N-M+1) { deque<pi> d; F0Rd(j,N) { while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back(); d.pb({X[i][j][k][l],j}); if (j <= N-M) { while (d.front().s >= j+M) d.pop_front(); X[i][j][k][l] = d.front().f; } } } } else { F0R(j,N-M+1) F0R(k,N-M+1) F0R(l,N-M+1) { deque<pi> d; F0Rd(i,N) { while (sz(d) && d.back().f >= X[i][j][k][l]) d.pop_back(); d.pb({X[i][j][k][l],i}); if (i <= N-M) { while (d.front().s >= i+M) d.pop_front(); X[i][j][k][l] = d.front().f; } } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; F0R(i,N) F0R(j,N) F0R(k,N) F0R(l,N) cin >> X[i][j][k][l]; F0Rd(i,4) solve(i); F0R(i,N-M+1) F0R(j,N-M+1) F0R(k,N-M+1) F0R(l,N-M+1) cout << X[i][j][k][l] << " "; } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#Verdict Execution timeMemoryGrader output
Fetching results...