From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- .../sliding_window_or_3405.cpp | 28 ++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 11_sliding_window_problems/sliding_window_or_3405.cpp (limited to '11_sliding_window_problems/sliding_window_or_3405.cpp') diff --git a/11_sliding_window_problems/sliding_window_or_3405.cpp b/11_sliding_window_problems/sliding_window_or_3405.cpp new file mode 100644 index 0000000..ba95e22 --- /dev/null +++ b/11_sliding_window_problems/sliding_window_or_3405.cpp @@ -0,0 +1,28 @@ +#include +#include + +// We pre-compute prefix and suffix or for non-overlapping windows of k +// elements, and we compute the sliding window or from those. +// https://codeforces.com/blog/entry/142846 + +int main() { + size_t n, k; + long long a, b, c, sol{0}; + std::cin >> n >> k; + std::vector v(n), pre(n), suf(n); + std::cin >> v[0] >> a >> b >> c; + + for (size_t i = 1; i < n; i++) + v[i] = (a*v[i-1] + b) % c; + + for (size_t i = 0; i < n; i++) + pre[i] = i % k == 0 ? v[i] : v[i] | pre[i-1]; + + for (size_t i = n; i > 0; i--) + suf[i-1] = i == n || (i-1) % k == 0 ? v[i-1] : v[i-1] | suf[i]; + + for (long long i = k-1; i < n; i++) + sol ^= pre[i] | suf[i-(k-1)]; + + std::cout << sol << "\n"; +} -- cgit v1.3