제출 #1269026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269026		proofy	최솟값 배열 (IZhO11_hyper)	C++20	100 / 100	318 ms	57948 KiB

hyper

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector

int n, m;

V<int> solve_1D(const V<int>& g) {
	deque<int> dq;
	V<int> res(n);
	for (int i = 0; i < n; i++) {
		while (!dq.empty() && dq.front() <= i - m) dq.pop_front();
		while (!dq.empty() && g[dq.back()] > g[i]) dq.pop_back();
		dq.push_back(i);
		if (i - m + 1 >= 0) res[i - m + 1] = g[dq.front()];
	}

	return res;
}

V<V<int>> solve_2D(const V<V<int>>& g) {
	V<deque<int>> dq(n);
	V<V<int>> res(n);
	for (int i = 0; i < n; i++) {
		V<int> g1(n);
		for (int j = 0; j < n; j++) {
			while (!dq[j].empty() && dq[j].front() <= i - m) dq[j].pop_front();
			while (!dq[j].empty() && g[dq[j].back()][j] > g[i][j]) dq[j].pop_back();
			dq[j].push_back(i);
			if (i - m + 1 >= 0) g1[j] = g[dq[j].front()][j];
		} 
		if (i - m + 1 >= 0) res[i - m + 1] = solve_1D(g1);
	}
	return res;
}

V<V<V<int>>> solve_3D(const V<V<V<int>>>& g) {
	V<V<deque<int>>> dq(n, V<deque<int>>(n));
	V<V<V<int>>> res(n);
	for (int i = 0; i < n; i++) {
		V<V<int>> g1(n, V<int>(n));
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++) {
				while (!dq[j][k].empty() && dq[j][k].front() <= i - m) dq[j][k].pop_front();
				while (!dq[j][k].empty() && g[dq[j][k].back()][j][k] > g[i][j][k]) dq[j][k].pop_back();
				dq[j][k].push_back(i);
				if (i - m + 1 >= 0) g1[j][k] = g[dq[j][k].front()][j][k];
			}
		if (i - m + 1 >= 0) res[i - m + 1] = solve_2D(g1);
	}
	return res;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	V<V<V<V<int>>>> g(n, V<V<V<int>>>(n, V<V<int>>(n, V<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 >> g[i][j][k][l];
					
	V<V<V<deque<int>>>> dq(n, V<V<deque<int>>>(n, V<deque<int>>(n)));
	V<V<V<V<int>>>> f(n);
	for (int i = 0; i < n; i++) {
		V<V<V<int>>> g1(n, V<V<int>>(n, V<int>(n)));
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				for (int l = 0; l < n; l++) {
					while (!dq[j][k][l].empty() && dq[j][k][l].front() <= i - m) dq[j][k][l].pop_front();
					while (!dq[j][k][l].empty() && g[dq[j][k][l].back()][j][k][l] > g[i][j][k][l]) dq[j][k][l].pop_back();
					dq[j][k][l].push_back(i);
					if (i - m + 1 >= 0) g1[j][k][l] = g[dq[j][k][l].front()][j][k][l];
				}
		if (i - m + 1 >= 0) f[i - m + 1] = solve_3D(g1);
	}
	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 l = 0; l + m - 1 < n; l++)
					cout << f[i][j][k][l] << " ";
}

• Subtask 1: 100 / 100