Initial commit

5 files changed, 108 insertions, 0 deletions

diff --git a/11_sliding_window_problems/a.out b/11_sliding_window_problems/a.out
new file mode 100755
index 0000000..8a06b5a
--- /dev/null
+++ b/11_sliding_window_problems/a.out
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 <algorithm>
+#include <deque>
+#include <iostream>
+#include <vector>
+
+int main() {
+        long long n, k, x, a, b, c;
+        std::cin >> n >> k >> x >> a >> b >> c;
+
+        std::vector<long long> v(k);
+        std::deque<long long> 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 <iostream>
+#include <vector>
+
+// 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<long long> 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 <iostream>
+#include <vector>
+
+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<long long> 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 <algorithm>
+#include <deque>
+#include <iostream>
+#include <vector>
+
+int main() {
+        long long n, k, x, a, b, c, m{0};
+        std::cin >> n >> k >> x >> a >> b >> c;
+
+        std::vector<long long> 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";
+}