結果
問題 | No.1867 Partitions and Inversions |
ユーザー | Forested |
提出日時 | 2022-01-20 21:00:57 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,857 ms / 5,000 ms |
コード長 | 3,925 bytes |
コンパイル時間 | 1,051 ms |
コンパイル使用メモリ | 86,056 KB |
実行使用メモリ | 144,536 KB |
最終ジャッジ日時 | 2023-08-15 20:58:26 |
合計ジャッジ時間 | 73,823 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1,776 ms
144,384 KB |
testcase_03 | AC | 1,752 ms
144,236 KB |
testcase_04 | AC | 1,769 ms
144,336 KB |
testcase_05 | AC | 1,751 ms
144,240 KB |
testcase_06 | AC | 1,750 ms
144,320 KB |
testcase_07 | AC | 1,771 ms
144,232 KB |
testcase_08 | AC | 1,761 ms
144,316 KB |
testcase_09 | AC | 1,753 ms
144,240 KB |
testcase_10 | AC | 1,705 ms
144,240 KB |
testcase_11 | AC | 1,719 ms
144,536 KB |
testcase_12 | AC | 1,719 ms
144,320 KB |
testcase_13 | AC | 1,759 ms
144,400 KB |
testcase_14 | AC | 1,737 ms
144,464 KB |
testcase_15 | AC | 1,741 ms
144,384 KB |
testcase_16 | AC | 1,740 ms
144,312 KB |
testcase_17 | AC | 1,794 ms
144,388 KB |
testcase_18 | AC | 1,743 ms
144,312 KB |
testcase_19 | AC | 1,767 ms
144,328 KB |
testcase_20 | AC | 1,771 ms
144,316 KB |
testcase_21 | AC | 1,823 ms
144,336 KB |
testcase_22 | AC | 1,781 ms
144,316 KB |
testcase_23 | AC | 1,771 ms
144,236 KB |
testcase_24 | AC | 1,791 ms
144,388 KB |
testcase_25 | AC | 1,781 ms
144,380 KB |
testcase_26 | AC | 1,789 ms
144,336 KB |
testcase_27 | AC | 1,773 ms
144,392 KB |
testcase_28 | AC | 1,751 ms
144,328 KB |
testcase_29 | AC | 1,802 ms
144,240 KB |
testcase_30 | AC | 1,857 ms
144,320 KB |
testcase_31 | AC | 1,759 ms
144,464 KB |
testcase_32 | AC | 2 ms
4,376 KB |
testcase_33 | AC | 1 ms
4,380 KB |
testcase_34 | AC | 1 ms
4,376 KB |
testcase_35 | AC | 2 ms
4,380 KB |
testcase_36 | AC | 1 ms
4,376 KB |
testcase_37 | AC | 2 ms
4,380 KB |
testcase_38 | AC | 31 ms
7,280 KB |
testcase_39 | AC | 31 ms
7,440 KB |
testcase_40 | AC | 30 ms
7,364 KB |
testcase_41 | AC | 30 ms
7,300 KB |
testcase_42 | AC | 30 ms
7,296 KB |
testcase_43 | AC | 694 ms
66,108 KB |
testcase_44 | AC | 695 ms
66,380 KB |
testcase_45 | AC | 697 ms
66,116 KB |
testcase_46 | AC | 692 ms
66,112 KB |
testcase_47 | AC | 680 ms
66,172 KB |
testcase_48 | AC | 679 ms
66,096 KB |
testcase_49 | AC | 679 ms
66,180 KB |
testcase_50 | AC | 688 ms
66,216 KB |
testcase_51 | AC | 700 ms
66,100 KB |
testcase_52 | AC | 689 ms
66,324 KB |
testcase_53 | AC | 687 ms
66,112 KB |
testcase_54 | AC | 704 ms
66,032 KB |
testcase_55 | AC | 704 ms
66,172 KB |
testcase_56 | AC | 702 ms
66,384 KB |
testcase_57 | AC | 693 ms
66,104 KB |
testcase_58 | AC | 688 ms
66,220 KB |
testcase_59 | AC | 693 ms
66,240 KB |
testcase_60 | AC | 689 ms
66,384 KB |
testcase_61 | AC | 692 ms
66,380 KB |
testcase_62 | AC | 689 ms
66,272 KB |
testcase_63 | AC | 1,620 ms
144,256 KB |
testcase_64 | AC | 1 ms
4,376 KB |
testcase_65 | AC | 2 ms
4,380 KB |
testcase_66 | AC | 2 ms
4,376 KB |
testcase_67 | AC | 1,477 ms
144,236 KB |
ソースコード
// ===== monotone_minima.hpp ===== #ifndef MONOTONE_MINIMA_HPP #define MONOTONE_MINIMA_HPP #include <vector> #include <numeric> template <typename F> std::vector<std::size_t> monotone_minima_sub(const F &f, const std::vector<std::size_t> &rows, std::size_t w) { if (rows.empty()) { return std::vector<std::size_t>(); } std::vector<std::size_t> red; red.reserve(rows.size() / 2); for (std::size_t i = 1; i < rows.size(); i += 2) { red.push_back(rows[i]); } std::vector<std::size_t> red_ans = monotone_minima_sub(f, red, w); std::vector<std::size_t> ans(rows.size()); for (std::size_t i = 0; i < red.size(); ++i) { ans[2 * i + 1] = red_ans[i]; } for (std::size_t i = 0; i < rows.size(); i += 2) { std::size_t l = (i == 0 ? 0 : ans[i - 1]); std::size_t r = (i == rows.size() - 1 ? w - 1 : ans[i + 1]); auto minimum = f(rows[i], l); std::size_t index = l; for (std::size_t j = l + 1; j <= r; ++j) { auto tmp = f(rows[i], j); if (tmp < minimum) { minimum = tmp; index = j; } } ans[i] = index; } return ans; } template <typename F> std::vector<std::size_t> monotone_minima(const F &f, std::size_t h, std::size_t w) { std::vector<std::size_t> rows(h); std::iota(rows.begin(), rows.end(), 0); return monotone_minima_sub(f, rows, w); } #endif // ===== monotone_minima.hpp ===== #include <iostream> #include <utility> #include <cassert> #include <algorithm> using usize = std::size_t; template <typename F> std::vector<usize> monge_maxima(const F &f, usize h, usize w) { const auto g = [&](std::size_t i, std::size_t j) { return -f(h - 1 - i, j); }; std::vector<std::size_t> ret = monotone_minima(g, h, w); std::reverse(ret.begin(), ret.end()); return ret; } std::vector<std::vector<usize>> calc_inv(std::vector<usize> p) { usize n = p.size(); std::vector<std::vector<usize>> sum(n + 1, std::vector<usize>(n + 1, 0)); for (usize i = 0; i < n; ++i) { sum[i + 1] = sum[i]; for (usize j = p[i]; j < n; ++j) { ++sum[i + 1][j + 1]; } } std::vector<std::vector<usize>> inv(n, std::vector<usize>(n + 1, 0)); for (usize i = 0; i < n; ++i) { usize s = 0; for (usize j = i; j < n; ++j) { s += sum[j][n] - sum[i][n] - sum[j][p[j]] + sum[i][p[j]]; inv[i][j + 1] = s; } } return inv; } void fast_dp( const std::vector<std::vector<usize>> &f, const std::vector<usize> &from, std::vector<usize> &to, usize l, usize r ) { if (l + 1 == r) { return; } usize mid = (l + r) / 2; fast_dp(f, from, to, l, mid); const auto jump = [&](usize i, usize j) -> long { i += mid; j += l; return from[j] + f[j][i]; }; std::vector<usize> max_index = monge_maxima(jump, r - mid, mid - l); for (usize i = 0; i < r - mid; ++i) { usize tmp = jump(i, max_index[i]); if (tmp > to[i + mid]) { to[i + mid] = tmp; } } fast_dp(f, from, to, mid, r); } std::vector<std::vector<usize>> calc_dp(std::vector<std::vector<usize>> inv) { usize n = inv.size(); std::vector<std::vector<usize>> dp(n + 1, std::vector<usize>(n + 1, 0)); for (usize i = 0; i < n; ++i) { fast_dp(inv, dp[i], dp[i + 1], i, n + 1); } return dp; } int main() { usize n; std::cin >> n; std::vector<std::size_t> p(n); for (std::size_t &ele : p) { std::cin >> ele; --ele; } std::vector<std::vector<usize>> inv = calc_inv(std::move(p)); usize all_inv = inv[0][n]; std::vector<std::vector<usize>> dp = calc_dp(std::move(inv)); for (usize i = 1; i <= n; ++i) { std::cout << all_inv - dp[i][n] << '\n'; } }