From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 11_sliding_window_problems/a.out | Bin 0 -> 65568 bytes .../sliding_window_minimum_3221.cpp | 29 +++++++++++++++++++++ .../sliding_window_or_3405.cpp | 28 ++++++++++++++++++++ .../sliding_window_sum_3220.cpp | 25 ++++++++++++++++++ .../sliding_window_xor_3426.cpp | 26 ++++++++++++++++++ 5 files changed, 108 insertions(+) create mode 100755 11_sliding_window_problems/a.out create mode 100644 11_sliding_window_problems/sliding_window_minimum_3221.cpp create mode 100644 11_sliding_window_problems/sliding_window_or_3405.cpp create mode 100644 11_sliding_window_problems/sliding_window_sum_3220.cpp create mode 100644 11_sliding_window_problems/sliding_window_xor_3426.cpp (limited to '11_sliding_window_problems') diff --git a/11_sliding_window_problems/a.out b/11_sliding_window_problems/a.out new file mode 100755 index 0000000..8a06b5a Binary files /dev/null and b/11_sliding_window_problems/a.out differ diff --git a/11_sliding_window_problems/sliding_window_minimum_3221.cpp b/11_sliding_window_problems/sliding_window_minimum_3221.cpp new file mode 100644 index 0000000..ef7485a --- /dev/null +++ b/11_sliding_window_problems/sliding_window_minimum_3221.cpp @@ -0,0 +1,29 @@ +#include +#include +#include +#include + +int main() { + long long n, k, x, a, b, c; + std::cin >> n >> k >> x >> a >> b >> c; + + std::vector v(k); + std::deque q; + for (long long i = 0; i < k; i++) { + v[i] = x; + while (!q.empty() && q.back() >= x) q.pop_back(); + q.push_back(x); + x = (a*x + b) % c; + } + + long long sol = q.front(); + for (long long i = 0; i < n-k; i++) { + if (q.front() == v[i%k]) q.pop_front(); + v[i%k] = (a*v[(i-1+k)%k] + b) % c; + while (!q.empty() && q.back() >= v[i%k]) q.pop_back(); + q.push_back(v[i%k]); + sol ^= q.front(); + } + + std::cout << sol << "\n"; +} 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"; +} diff --git a/11_sliding_window_problems/sliding_window_sum_3220.cpp b/11_sliding_window_problems/sliding_window_sum_3220.cpp new file mode 100644 index 0000000..9096b75 --- /dev/null +++ b/11_sliding_window_problems/sliding_window_sum_3220.cpp @@ -0,0 +1,25 @@ +#include +#include + +int main() { + size_t n, k; + long long x, a, b, c, sum{0}, sol{0}; + std::cin >> n >> k >> x >> a >> b >> c; + + std::vector v(k); + for (size_t i = 0; i < k; i++) { + sum += x; + v[i] = x; + x = (a*x + b) % c; + } + + sol = sum; + for (size_t i = 0; i < n-k; i++) { + sum -= v[i%k]; + v[i%k] = (a*v[(i-1+k)%k] + b) % c; + sum += v[i%k]; + sol ^= sum; + } + + std::cout << sol << "\n"; +} diff --git a/11_sliding_window_problems/sliding_window_xor_3426.cpp b/11_sliding_window_problems/sliding_window_xor_3426.cpp new file mode 100644 index 0000000..0f21ce3 --- /dev/null +++ b/11_sliding_window_problems/sliding_window_xor_3426.cpp @@ -0,0 +1,26 @@ +#include +#include +#include +#include + +int main() { + long long n, k, x, a, b, c, m{0}; + std::cin >> n >> k >> x >> a >> b >> c; + + std::vector v(k); + for (long long i = 0; i < k; i++) { + v[i] = x; + m ^= x; + x = (a*x + b) % c; + } + + long long sol{m}; + for (long long i = 0; i < n-k; i++) { + m ^= v[i%k]; + v[i%k] = (a*v[(i-1+k)%k] + b) % c; + m ^= v[i%k]; + sol ^= m; + } + + std::cout << sol << "\n"; +} -- cgit v1.3