結果
問題 |
No.3265 地元に帰れば天才扱い!
|
ユーザー |
|
提出日時 | 2025-08-07 23:52:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 5,220 bytes |
コンパイル時間 | 5,423 ms |
コンパイル使用メモリ | 283,984 KB |
実行使用メモリ | 816,420 KB |
最終ジャッジ日時 | 2025-09-06 12:30:54 |
合計ジャッジ時間 | 8,709 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 RE * 1 |
other | MLE * 1 -- * 20 |
ソースコード
#include <bits/stdc++.h> namespace MyLib { template<typename T, class Picker, T default_value> class LiteralSegmentTree { protected: std::vector<std::vector<T>> containers; public: constexpr LiteralSegmentTree(const std::vector<T>& initializer) { containers.clear(); if (initializer.size() == 0) return; else if (initializer.size() == 1) { containers.emplace_back(1, initializer[0]); return; } uint_fast32_t l = 0, r = 30; while (l + 1 < r) { const auto c = (l + r) >> 1; if (((uint_fast32_t)1 << c) < initializer.size()) l = c; else r = c; } containers.emplace_back((uint_fast32_t)1 << r); uint_fast32_t i; for (i = 0; i != initializer.size(); ++i) containers[0][i] = initializer[i]; for (; i != ((uint_fast32_t)1 << r); ++i) containers[0][i] = default_value; for (--r; r != 0; --r) { containers.emplace_back((uint_fast32_t)1 << r); for (i = 0; i != ((uint_fast32_t)1 << r); ++i) containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]); } containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1])); } constexpr LiteralSegmentTree(std::vector<T>&& initializer) { containers.clear(); if (initializer.size() == 0) return; uint_fast32_t l = 0, r = 30; while (l + 1 < r) { const auto c = (l + r) >> 1; if (((uint_fast32_t)1 << c) < initializer.size()) l = c; else r = c; } containers.emplace_back(std::move(initializer)); containers[0].resize((uint_fast32_t)1 << r, default_value); uint_fast32_t i; for (--r; r != 0; --r) { containers.emplace_back((uint_fast32_t)1 << r); for (i = 0; i != ((uint_fast32_t)1 << r); ++i) containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]); } containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1])); } constexpr LiteralSegmentTree(const uint_fast32_t n) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, default_value)) { } constexpr LiteralSegmentTree(const uint_fast32_t n, const T initial_value) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, initial_value)) { } constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; } constexpr uint_fast32_t size() const noexcept { return containers[0].size(); } constexpr uint_fast32_t layer() const noexcept { return containers.size(); } constexpr T update(uint_fast32_t index, const T value) noexcept { containers[0][index] = value; index >>= 1; for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1) containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]); return value; } constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept { if (containers.size() == 0 || end_index > containers[0].size()) return default_value; T ret_l = default_value, ret_r = default_value; for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer) { if (first_index & 1) ret_l = Picker()(ret_l, containers[cur_layer][first_index]), ++first_index; if (end_index & 1) ret_r = Picker()(containers[cur_layer][end_index - 1], ret_r); } return Picker()(ret_l, ret_r); } }; } // セグメントツリー解法 static inline constexpr std::vector<uint_fast64_t> solve(const uint_fast32_t N, const uint_fast32_t Q, std::vector<uint_fast64_t>&& A, std::vector<uint_fast32_t>& X, const std::vector<uint_fast32_t>& Y, const std::vector<uint_fast32_t>& L, const std::vector<uint_fast32_t>& R) noexcept { uint_fast64_t sum = 0; std::vector<uint_fast64_t> ans(Q); MyLib::LiteralSegmentTree<uint_fast64_t, std::plus<uint_fast64_t>, 0> lst(std::move(A)); MyLib::LiteralSegmentTree<uint_fast32_t, std::plus<uint_fast32_t>, 0> imos_weight(N + 1, 0); for (uint_fast32_t i = 0; i != Q; ++i) { const uint_fast32_t weight = imos_weight.range_pick_up(0, X[i]); // imos 法で一点の重みを取得する sum -= lst[X[i] - 1] * weight; lst.update(X[i] - 1, Y[i]); sum += lst[X[i] - 1] * weight; ans[i] = (sum += lst.range_pick_up(L[i] - 1, R[i])); imos_weight.update(L[i] - 1, imos_weight[L[i] - 1] + 1), imos_weight.update(R[i], imos_weight[R[i]] - 1); // imos 法で区間の重みを増やす } return ans; } static inline void output(const uint_fast32_t Q, const std::vector<uint_fast64_t>& ans) noexcept { for (uint_fast32_t i = 0; i != Q; ++i) std::cout << ans[i] << '\n'; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); uint_fast32_t N, Q, i; std::cin >> N; std::vector<uint_fast64_t> A(N); for (i = 0; i != N; ++i) std::cin >> A[i]; std::cin >> Q; std::vector<uint_fast32_t> X(Q), Y(Q), L(Q), R(Q); for (i = 0; i != Q; ++i) std::cin >> X[i] >> Y[i] >> L[i] >> R[i]; output(Q, solve(N, Q, std::move(A), X, Y, L, R)); return 0; }