Submission #412284

#TimeUsernameProblemLanguageResultExecution timeMemory
412284ritul_kr_singhHyper-minimum (IZhO11_hyper)C++17
100 / 100
495 ms40376 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m; cin >> n >> m; --m;
	int a[n][n][n][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 : a[i][j][k]) cin >> l;
	
	for(int i=0; i<n; ++i){
		for(int j=0; j<n; ++j){
			for(int k=0; k<n; ++k){
				deque<int> q;
				for(int l=0; l<n; ++l){
					if(!q.empty() && q.front() < l-m) q.pop_front();
					while(!q.empty() && a[i][j][k][q.back()] >= a[i][j][k][l]) q.pop_back();
					q.push_back(l);
					if(l >= m) a[i][j][k][l-m] = a[i][j][k][q.front()];
				}
			}
			for(int l=0; l<n-m; ++l){
				deque<int> q;
				for(int k=0; k<n; ++k){
					if(!q.empty() && q.front() < k-m) q.pop_front();
					while(!q.empty() && a[i][j][q.back()][l] >= a[i][j][k][l]) q.pop_back();
					q.push_back(k);
					if(k >= m) a[i][j][k-m][l] = a[i][j][q.front()][l];
				}
			}
		}
	}

	for(int k=0; k<n-m; ++k){
		for(int l=0; l<n-m; ++l){
			for(int i=0; i<n; ++i){
				deque<int> q;
				for(int j=0; j<n; ++j){
					if(!q.empty() && q.front() < j-m) q.pop_front();
					while(!q.empty() && a[i][q.back()][k][l] >= a[i][j][k][l]) q.pop_back();
					q.push_back(j);
					if(j >= m) a[i][j-m][k][l] = a[i][q.front()][k][l];
				}
			}
			for(int j=0; j<n-m; ++j){
				deque<int> q;
				for(int i=0; i<n; ++i){
					if(!q.empty() && q.front() < i-m) q.pop_front();
					while(!q.empty() && a[q.back()][j][k][l] >= a[i][j][k][l]) q.pop_back();
					q.push_back(i);
					if(i >= m) a[i-m][j][k][l] = a[q.front()][j][k][l];
				}
			}
		}
	}

	for(int i=0; i<n-m; ++i)
		for(int j=0; j<n-m; ++j)
			for(int k=0; k<n-m; ++k)
				for(int l=0; l<n-m; ++l)
					cout << a[i][j][k][l] << ' ';
}
#Verdict Execution timeMemoryGrader output
Fetching results...