답안 #972751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972751	2024-05-01T05:30:27 Z	arush_agu	최솟값 배열 (IZhO11_hyper)	C++17	100 / 100	434 ms	54928 KB

hyper

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

struct MinQ {
  vii s1, s2;

  void add(int x) {
    int mn = s1.empty() ? x : min(s1.back().second, x);
    s1.push_back({x, mn});
  }

  void pop() {
    if (s1.empty() && s2.empty())
      return;
    if (s2.empty()) {
      while (!s1.empty()) {
        auto [x, pmn] = s1.back();
        s1.pop_back();
        int mn = s2.empty() ? x : min(pmn, s2.back().second);
        s2.push_back({x, mn});
      }
    }
    s2.pop_back();
  }

  int mn() {
    if (s1.empty() && s2.empty())
      return INF;
    if (s1.empty() || s2.empty())
      return s1.empty() ? s2.back().second : s1.back().second;
    return min(s1.back().second, s2.back().second);
  }

  int sz() { return s1.size() + s2.size(); }
};

void solve() {
  int n, m;
  cin >> n >> 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 = 0; l < n; l++)
          cin >> a[i][j][k][l];

  int one[n][n][n][n - m + 1];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) {
        multiset<int> ms;
        for (int l = 0; l < m; l++)
          ms.insert(a[i][j][k][l]);
        one[i][j][k][0] = *ms.begin();
        for (int l = 1; l < n - m + 1; l++) {
          ms.erase(ms.find(a[i][j][k][l - 1]));
          ms.insert(a[i][j][k][l + m - 1]);
          one[i][j][k][l] = *ms.begin();
        }
      }

  int two[n][n][n - m + 1][n - m + 1];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int l = 0; l < n - m + 1; l++) {
        multiset<int> ms;
        for (int k = 0; k < m; k++)
          ms.insert(one[i][j][k][l]);
        two[i][j][0][l] = *ms.begin();
        for (int k = 1; k < n - m + 1; k++) {
          ms.erase(ms.find(one[i][j][k - 1][l]));
          ms.insert(one[i][j][k + m - 1][l]);
          two[i][j][k][l] = *ms.begin();
        }
      }

  int three[n][n - m + 1][n - m + 1][n - m + 1];
  for (int i = 0; i < n; i++)
    for (int k = 0; k < n - m + 1; k++)
      for (int l = 0; l < n - m + 1; l++) {
        multiset<int> ms;
        for (int j = 0; j < m; j++)
          ms.insert(two[i][j][k][l]);
        three[i][0][k][l] = *ms.begin();
        for (int j = 1; j < n - m + 1; j++) {
          ms.erase(ms.find(two[i][j - 1][k][l]));
          ms.insert(two[i][j + m - 1][k][l]);
          three[i][j][k][l] = *ms.begin();
        }
      }

  int four[n - m + 1][n - m + 1][n - m + 1][n - m + 1];
  for (int j = 0; j < n - m + 1; j++)
    for (int k = 0; k < n - m + 1; k++)
      for (int l = 0; l < n - m + 1; l++) {
        multiset<int> ms;
        for (int i = 0; i < m; i++)
          ms.insert(three[i][j][k][l]);
        four[0][j][k][l] = *ms.begin();
        for (int i = 1; i < n - m + 1; i++) {
          ms.erase(ms.find(three[i - 1][j][k][l]));
          ms.insert(three[i + m - 1][j][k][l]);
          four[i][j][k][l] = *ms.begin();
        }
      }

  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 << four[i][j][k][l] << " ";
  cout << "\n";
}

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

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

hyper.cpp: In function 'int main()':
hyper.cpp:210:11: warning: unused variable 'start' [-Wunused-variable]
  210 |   clock_t start = clock();
      |           ^~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	3 ms	604 KB	Output is correct
6	Correct	12 ms	1556 KB	Output is correct
7	Correct	9 ms	1112 KB	Output is correct
8	Correct	24 ms	2728 KB	Output is correct
9	Correct	42 ms	6740 KB	Output is correct
10	Correct	30 ms	3152 KB	Output is correct
11	Correct	99 ms	9044 KB	Output is correct
12	Correct	204 ms	16976 KB	Output is correct
13	Correct	119 ms	11924 KB	Output is correct
14	Correct	225 ms	27332 KB	Output is correct
15	Correct	323 ms	45904 KB	Output is correct
16	Correct	190 ms	17996 KB	Output is correct
17	Correct	279 ms	24140 KB	Output is correct
18	Correct	434 ms	54928 KB	Output is correct
19	Correct	374 ms	31648 KB	Output is correct
20	Correct	239 ms	21924 KB	Output is correct