| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 515758 | 2022-01-19T15:14:35 Z | Be_dos | 최솟값 배열 (IZhO11_hyper) | C++17 | 872 ms | 35764 KB |
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>
struct SuperStack {
std::vector<std::pair<int32_t, int32_t> > data;
int32_t get() {
return data.empty() ? INT32_MAX : data.back().second;
}
void push_back(int32_t x) {
data.emplace_back(x, data.empty() ? x : std::min(data.back().second, x));
}
void pop_back() {
data.pop_back();
}
};
struct SlidingMin {
SuperStack left, right;
int32_t get() {
return std::min(left.get(), right.get());
}
void push_back(int32_t x) {
right.push_back(x);
}
void pop_back() {
if(left.data.size() == 0) {
for(int32_t i = right.data.size() / 2; i >= 0; i--)
left.push_back(right.data[i].first);
SuperStack right2;
for(int32_t i = right.data.size() / 2 + 1; i < right.data.size(); i++)
right2.push_back(right.data[i].first);
right = right2;
}
left.pop_back();
}
};
int main() {
int32_t n, m;
std::cin >> n >> m;
int32_t**** arr = new int32_t***[n];
for(int32_t i = 0; i < n; i++) {
arr[i] = new int32_t**[n];
for(int32_t j = 0; j < n; j++) {
arr[i][j] = new int32_t*[n];
for(int32_t k = 0; k < n; k++) {
arr[i][j][k] = new int32_t[n];
for(int32_t p = 0; p < n; p++) {
std::cin >> arr[i][j][k][p];
}
}
}
}
for(int32_t i = 0; i < n; i++) {
for(int32_t j = 0; j < n; j++) {
for(int32_t k = 0; k < n; k++) {
SlidingMin min;
for(int32_t p = 0; p < n; p++)
if(p + m > n)
arr[i][j][k][p] = INT32_MAX;
else {
if(p == 0)
for(int32_t q = 0; q < m; q++)
min.push_back(arr[i][j][k][q]);
else {
min.push_back(arr[i][j][k][p + m - 1]);
min.pop_back();
}
arr[i][j][k][p] = min.get();
}
}
}
}
for(int32_t i = 0; i < n; i++) {
for(int32_t j = 0; j < n; j++) {
for(int32_t p = 0; p < n; p++) {
SlidingMin min;
for(int32_t k = 0; k < n; k++)
if(k + m > n)
arr[i][j][k][p] = INT32_MAX;
else {
if(k == 0)
for(int32_t q = 0; q < m; q++)
min.push_back(arr[i][j][q][p]);
else {
min.push_back(arr[i][j][k + m - 1][p]);
min.pop_back();
}
arr[i][j][k][p] = min.get();
}
}
}
}
for(int32_t i = 0; i < n; i++) {
for(int32_t k = 0; k < n; k++) {
for(int32_t p = 0; p < n; p++) {
SlidingMin min;
for(int32_t j = 0; j < n; j++)
if(j + m > n)
arr[i][j][k][p] = INT32_MAX;
else {
if(j == 0)
for(int32_t q = 0; q < m; q++)
min.push_back(arr[i][q][k][p]);
else {
min.push_back(arr[i][j + m - 1][k][p]);
min.pop_back();
}
arr[i][j][k][p] = min.get();
}
}
}
}
for(int32_t j = 0; j < n; j++) {
for(int32_t k = 0; k < n; k++) {
for(int32_t p = 0; p < n; p++) {
SlidingMin min;
for(int32_t i = 0; i < n; i++)
if(i + m > n)
arr[i][j][k][p] = INT32_MAX;
else {
if(i == 0)
for(int32_t q = 0; q < m; q++)
min.push_back(arr[q][j][k][p]);
else {
min.push_back(arr[i + m - 1][j][k][p]);
min.pop_back();
}
arr[i][j][k][p] = min.get();
}
}
}
}
for(int32_t i = 0; i <= n - m; i++) {
for(int32_t j = 0; j <= n - m; j++) {
for(int32_t k = 0; k <= n - m; k++) {
for(int32_t p = 0; p <= n - m; p++) {
std::cout << arr[i][j][k][p] << " ";
}
}
}
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 288 KB | Output is correct |
| 2 | Correct | 1 ms | 300 KB | Output is correct |
| 3 | Correct | 5 ms | 416 KB | Output is correct |
| 4 | Correct | 7 ms | 436 KB | Output is correct |
| 5 | Correct | 6 ms | 436 KB | Output is correct |
| 6 | Correct | 28 ms | 1132 KB | Output is correct |
| 7 | Correct | 26 ms | 1048 KB | Output is correct |
| 8 | Correct | 87 ms | 2620 KB | Output is correct |
| 9 | Correct | 89 ms | 4356 KB | Output is correct |
| 10 | Correct | 86 ms | 2740 KB | Output is correct |
| 11 | Correct | 219 ms | 6748 KB | Output is correct |
| 12 | Correct | 423 ms | 13268 KB | Output is correct |
| 13 | Correct | 419 ms | 12148 KB | Output is correct |
| 14 | Correct | 492 ms | 18004 KB | Output is correct |
| 15 | Correct | 732 ms | 29220 KB | Output is correct |
| 16 | Correct | 585 ms | 17708 KB | Output is correct |
| 17 | Correct | 685 ms | 19144 KB | Output is correct |
| 18 | Correct | 872 ms | 35764 KB | Output is correct |
| 19 | Correct | 818 ms | 24704 KB | Output is correct |
| 20 | Correct | 816 ms | 22664 KB | Output is correct |