結果
問題 | No.924 紲星 |
ユーザー | noshi91 |
提出日時 | 2019-11-08 21:45:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,468 ms / 4,000 ms |
コード長 | 6,710 bytes |
コンパイル時間 | 866 ms |
コンパイル使用メモリ | 86,148 KB |
実行使用メモリ | 106,484 KB |
最終ジャッジ日時 | 2023-10-13 03:44:16 |
合計ジャッジ時間 | 14,414 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 4 ms
4,352 KB |
testcase_04 | AC | 3 ms
4,352 KB |
testcase_05 | AC | 4 ms
4,352 KB |
testcase_06 | AC | 4 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 1,444 ms
106,240 KB |
testcase_09 | AC | 1,399 ms
106,304 KB |
testcase_10 | AC | 1,451 ms
106,484 KB |
testcase_11 | AC | 1,369 ms
106,108 KB |
testcase_12 | AC | 1,468 ms
106,192 KB |
testcase_13 | AC | 709 ms
40,472 KB |
testcase_14 | AC | 710 ms
26,540 KB |
testcase_15 | AC | 641 ms
32,824 KB |
testcase_16 | AC | 485 ms
92,060 KB |
testcase_17 | AC | 1,085 ms
41,636 KB |
testcase_18 | AC | 2 ms
4,352 KB |
ソースコード
#include <algorithm> #include <array> #include <bitset> #include <cstddef> #include <tuple> #include <utility> #include <vector> template <std::size_t BitLength, class Abelian> struct foldable_wavelet_matrix { using mapped_structure = Abelian; using mapped_type = typename mapped_structure::value_type; using key_type = std::bitset<BitLength>; struct bitvector { struct node_type; using container_type = std::vector<node_type>; using size_type = typename container_type::size_type; struct node_type { size_type count; mapped_type sum; constexpr node_type() : count(static_cast<size_type>(0)), sum(mapped_structure::identity()) {} }; container_type vec; constexpr bitvector() : vec() {} constexpr void resize(const size_type size) { vec.resize(size + static_cast<size_type>(1)); } constexpr void set(const size_type index) { vec[index].count = static_cast<size_type>(1); } template <class InputIterator> constexpr void build(const std::vector<InputIterator> &a) { for (size_type i = a.size(); i != static_cast<size_type>(0);) { --i; vec[i].count += vec[i + static_cast<size_type>(1)].count; vec[i].sum = mapped_structure::operation( a[i]->second, vec[i + static_cast<size_type>(1)].sum); } } constexpr size_type count(const size_type index) const { return vec[index].count; } constexpr size_type zeros() const { return vec.front().count; } constexpr mapped_type fold(const size_type first, const size_type last) const { return mapped_structure::operation( vec[first].sum, mapped_structure::inverse(vec[last].sum)); } }; using size_type = typename bitvector::size_type; std::array<bitvector, BitLength> matrix; constexpr foldable_wavelet_matrix() : matrix() {} template <class InputIterator> explicit constexpr foldable_wavelet_matrix(InputIterator first, const InputIterator last) { using iterator = InputIterator; const size_type size = static_cast<size_type>(std::distance(first, last)); std::vector<iterator> cur, pre; cur.reserve(size); for (; first != last; ++first) { cur.push_back(first); } pre = cur; std::size_t i = BitLength; while (i != static_cast<std::size_t>(0)) { --i; bitvector &vec = matrix[i]; vec.resize(size); std::swap(cur, pre); typename std::vector<iterator>::iterator zero_itr = cur.begin(), one_itr = cur.end(); for (size_type k = static_cast<size_type>(0); zero_itr != one_itr; ++k) { if (pre[k]->first.test(i)) { --one_itr; *one_itr = pre[k]; } else { vec.set(k); *zero_itr = pre[k]; ++zero_itr; } } std::reverse(one_itr, cur.end()); vec.build(cur); } } constexpr std::tuple<mapped_type, mapped_type, mapped_type> fold_leg(size_type first, size_type last, const key_type &key) const { mapped_type less = mapped_structure::identity(), greater = mapped_structure::identity(); std::size_t i = BitLength; while (i != static_cast<std::size_t>(0)) { --i; const bitvector &vec = matrix[i]; const size_type f = vec.count(first), l = vec.count(last), z = vec.zeros(); if (key.test(i)) { less = mapped_structure::operation(std::move(less), vec.fold(z - f, z - l)); first += f; last += l; } else { greater = mapped_structure::operation(vec.fold(first + f, last + l), std::move(greater)); first = z - f; last = z - l; } } return std::forward_as_tuple( std::move(less), matrix.front().fold(first, last), std::move(greater)); } constexpr mapped_type fold_range(const size_type first, const size_type last, const key_type &lower, const key_type &upper) const { return mapped_structure::operation( mapped_structure::inverse(std::get<0>(fold_leg(first, last, lower))), std::get<0>(fold_leg(first, last, upper))); } constexpr std::pair<mapped_type, mapped_type> fold_quantile(size_type first, size_type last, size_type k) const { mapped_type less = mapped_structure::identity(), greater = mapped_structure::identity(); std::size_t i = BitLength; while (i != static_cast<std::size_t>(0)) { --i; const bitvector &vec = matrix[i]; const size_type f = vec.count(first), l = vec.count(last), z = vec.zeros(); if (f - l <= k) { k -= f - l; less = mapped_structure::operation(std::move(less), vec.fold(z - f, z - l)); first += f; last += l; } else { greater = mapped_structure::operation(vec.fold(first + f, last + l), std::move(greater)); first = z - f; last = z - l; } } return std::make_pair( mapped_structure::operation(std::move(less), matrix.front().fold(first, first + k)), mapped_structure::operation(matrix.front().fold(first + k, last), std::move(greater))); } }; template <class T> class plus_abelian { public: using value_type = T; static value_type operation(const value_type &x, const value_type &y) { return x + y; } static value_type identity() { return static_cast<value_type>(0); } static value_type inverse(const value_type &x) { return -x; } static value_type reverse(const value_type &x) { return x; } }; #include <iostream> #include <vector> int main() { using u64 = unsigned long long; using i64 = long long; using fwm_t = foldable_wavelet_matrix<31, plus_abelian<i64>>; int n, q; std::cin >> n >> q; std::vector<std::pair<typename fwm_t::key_type, i64>> a(n); for (auto &e : a) { i64 temp; std::cin >> temp; e = {temp + 1000000000, temp}; } fwm_t wm(a.cbegin(), a.cend()); for (int i = 0; i < q; ++i) { int l, r; std::cin >> l >> r; l -= 1; const i64 sep = (r - l) / 2; const auto v = wm.fold_quantile(l, r, sep); const auto u = wm.fold_quantile(l, r, sep + 1); const i64 base = u.first - v.first; std::cout << base * sep - v.first + v.second - base * (r - l - sep) << std::endl; } }