結果
問題 |
No.3205 Range Pairwise Xor Query
|
ユーザー |
|
提出日時 | 2025-07-20 09:31:38 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 1,543 bytes |
コンパイル時間 | 1,065 ms |
コンパイル使用メモリ | 90,120 KB |
実行使用メモリ | 50,160 KB |
最終ジャッジ日時 | 2025-07-20 09:31:46 |
合計ジャッジ時間 | 6,130 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#include <iostream> #include <cstdint> #include <array> #include <vector> static inline constexpr std::vector<std::array<uint_fast32_t, 26>> prepare(const uint_fast32_t N, const std::vector<uint_fast32_t>& A) noexcept { std::vector<std::array<uint_fast32_t, 26>> csum_count(N + 1); for (uint_fast32_t i = 0; i != N; ++i) for (uint_fast32_t j = 0; j != 26; ++j) csum_count[i + 1][j] = csum_count[i][j] + ((A[i] >> j) & 1); return csum_count; } static inline constexpr std::vector<uint_fast64_t> solve(const uint_fast32_t Q, const std::vector<uint_fast32_t>& L, const std::vector<uint_fast32_t>& R, const std::vector<std::array<uint_fast32_t, 26>>& csum_count) noexcept { std::vector<uint_fast64_t> ans(Q, 0); for (uint_fast32_t i = 0; i != Q; ++i) for (uint_fast32_t j = 0; j != 26; ++j) { const uint_fast32_t count[2] = { (R[i] + 1 - L[i]) - (csum_count[R[i]][j] - csum_count[L[i] - 1][j]), csum_count[R[i]][j] - csum_count[L[i] - 1][j] }; ans[i] += (static_cast<uint_fast64_t>(count[0]) * count[1]) << j; } 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 >> Q; std::vector<uint_fast32_t> A(N), L(Q), R(Q); for (i = 0; i != N; ++i) std::cin >> A[i]; for (i = 0; i != Q; ++i) std::cin >> L[i] >> R[i]; output(Q, solve(Q, L, R, prepare(N, A))); return 0; }