제출 #913550

#제출 시각아이디문제언어결과실행 시간메모리
913550daoquanglinh2007최솟값 배열 (IZhO11_hyper)C++17
0 / 100
273 ms53056 KiB
#include <bits/stdc++.h>
using namespace std;

const int NM = 30;

int N, M, a[NM+5][NM+5][NM+5][NM+5];
int f1[NM+5][NM+5][NM+5][NM+5], f2[NM+5][NM+5][NM+5][NM+5], f3[NM+5][NM+5][NM+5][NM+5], f4[NM+5][NM+5][NM+5][NM+5];
deque <int> dq;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++)
				for (int l = 1; l <= N; l++)
					cin >> a[i][j][k][l];
					
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int k = 1; k <= N; k++){
				dq.clear();
				for (int l = 1; l <= N; l++){
					if (l > M && dq.front() == l-M) dq.pop_front();
					while (!dq.empty() && a[i][j][k][l] <= a[i][j][k][dq.back()]) dq.pop_back();
					dq.push_back(l);
					if (l >= M) f1[i][j][k][l] = a[i][j][k][dq.front()];
				}
			}
			
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			for (int l = M; l <= N; l++){
				dq.clear();
				for (int k = 1; k <= N; k++){
					if (k > M && dq.front() == k-M) dq.pop_front();
					while (!dq.empty() && f1[i][j][k][l] <= f1[i][j][dq.back()][l]) dq.pop_back();
					dq.push_back(k);
					if (k >= M) f2[i][j][k][l] = f1[i][j][dq.front()][l];
				}
			}
	for (int i = 1; i <= N; i++)
		for (int k = M; k <= N; k++)
			for (int l = M; l <= N; l++){
				dq.clear();
				for (int j = 1; j <= N; j++){
					if (j > M && dq.front() == j-M) dq.pop_front();
					while (!dq.empty() && f2[i][j][k][l] <= f2[i][dq.back()][k][l]) dq.pop_back();
					dq.push_back(j);
					if (j >= M) f3[i][j][k][l] = f2[i][dq.front()][k][l];
				}
			}
	for (int j = M; j <= N; j++)
		for (int k = M; k <= N; k++)
			for (int l = M; l <= N; l++){
				dq.clear();
				for (int i = 1; i <= N; i++){
					if (i > M && dq.front() == i-M) dq.pop_front();
					while (!dq.empty() && f3[i][j][k][l] <= f3[dq.back()][j][k][l]) dq.pop_back();
					dq.push_back(i);
					if (i >= M) f4[i][j][k][l] = f3[dq.front()][j][k][l];
				}
			}
	for (int i = M; i <= N; i++)
		for (int j = M; j <= N; j++)
			for (int k = M; k <= N; k++)
				for (int l = M; l <= N; l++)
					cout << f4[i][j][k][l] << ' ';
					
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...