From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 6 Jul 2026 19:08:08 +0200
Subject: Initial commit

---
 02_sorting_and_searching/a.out                     | Bin 0 -> 18400 bytes
 02_sorting_and_searching/apartments_1084.cpp       |  27 ++++++++++++
 .../collecting_numbers_2216.cpp                    |  46 +++++++++++++++++++++
 02_sorting_and_searching/concert_tickets_1091.cpp  |  25 +++++++++++
 02_sorting_and_searching/distinct_numbers_1621.cpp |  13 ++++++
 02_sorting_and_searching/ferris_wheel_1090.cpp     |  17 ++++++++
 .../maximum_subarray_sum_1643.cpp                  |  19 +++++++++
 02_sorting_and_searching/missing_coin_sum_2183.cpp |  16 +++++++
 02_sorting_and_searching/movie_festival_1629.cpp   |  21 ++++++++++
 02_sorting_and_searching/playlist_1141.cpp         |  22 ++++++++++
 .../restaurant_customers_1619.cpp                  |  24 +++++++++++
 02_sorting_and_searching/room_allocation_1164.cpp  |  38 +++++++++++++++++
 02_sorting_and_searching/stick_lengths_1074.cpp    |  16 +++++++
 .../sum_of_two_values_1640.cpp                     |  27 ++++++++++++
 02_sorting_and_searching/towers_1063.cpp           |  17 ++++++++
 15 files changed, 328 insertions(+)
 create mode 100755 02_sorting_and_searching/a.out
 create mode 100644 02_sorting_and_searching/apartments_1084.cpp
 create mode 100644 02_sorting_and_searching/collecting_numbers_2216.cpp
 create mode 100644 02_sorting_and_searching/concert_tickets_1091.cpp
 create mode 100644 02_sorting_and_searching/distinct_numbers_1621.cpp
 create mode 100644 02_sorting_and_searching/ferris_wheel_1090.cpp
 create mode 100644 02_sorting_and_searching/maximum_subarray_sum_1643.cpp
 create mode 100644 02_sorting_and_searching/missing_coin_sum_2183.cpp
 create mode 100644 02_sorting_and_searching/movie_festival_1629.cpp
 create mode 100644 02_sorting_and_searching/playlist_1141.cpp
 create mode 100644 02_sorting_and_searching/restaurant_customers_1619.cpp
 create mode 100644 02_sorting_and_searching/room_allocation_1164.cpp
 create mode 100644 02_sorting_and_searching/stick_lengths_1074.cpp
 create mode 100644 02_sorting_and_searching/sum_of_two_values_1640.cpp
 create mode 100644 02_sorting_and_searching/towers_1063.cpp

(limited to '02_sorting_and_searching')

diff --git a/02_sorting_and_searching/a.out b/02_sorting_and_searching/a.out
new file mode 100755
index 0000000..1156f0d
Binary files /dev/null and b/02_sorting_and_searching/a.out differ
diff --git a/02_sorting_and_searching/apartments_1084.cpp b/02_sorting_and_searching/apartments_1084.cpp
new file mode 100644
index 0000000..b5ee47f
--- /dev/null
+++ b/02_sorting_and_searching/apartments_1084.cpp
@@ -0,0 +1,27 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+std::vector<int> readn(int n) {
+	std::vector<int> v(n);
+	for (int i = 0; i < n; i++)
+		std::cin >> v[i];
+	return v;
+}
+
+int main() {
+	int n, m, k;
+	std::cin >> n >> m >> k;
+	auto a = readn(n);
+	auto b = readn(m);
+	std::sort(a.begin(), a.end());
+	std::sort(b.begin(), b.end());
+
+	size_t s{0}, i{0}, j{0};
+	while (i < a.size() && j < b.size()) {
+		if (b[j] > a[i] + k) i++;
+		else if (b[j] < a[i] - k) j++;
+		else { s++; i++; j++; }
+	}
+	std::cout << s << "\n";
+}
diff --git a/02_sorting_and_searching/collecting_numbers_2216.cpp b/02_sorting_and_searching/collecting_numbers_2216.cpp
new file mode 100644
index 0000000..1adcf28
--- /dev/null
+++ b/02_sorting_and_searching/collecting_numbers_2216.cpp
@@ -0,0 +1,46 @@
+#include <iostream>
+#include <vector>
+
+int main() {
+	size_t n, x, s{1}, l{0};
+	std::cin >> n;
+	std::vector<size_t> b(n);
+	for (size_t i = 0; i < n; i++) {
+		std::cin >> x;
+		b[x-1] = i;
+	}
+	for (size_t i = 0; i < n; i++) {
+		s += b[i] < l;
+		l = b[i];
+	}
+	std::cout << s << "\n";
+}
+
+
+// The code below solves a different problem: it finds the minimum number
+// of ascending chains needed to partition the given list of numbers.
+
+#if 0
+
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	size_t n;
+	std::vector<size_t> s;
+	std::cin >> n;
+	for (size_t i = 0; i < n; i++) {
+		size_t x;
+		std::cin >> x;
+		auto it = std::lower_bound(
+		    s.begin(), s.end(), x, std::greater<size_t>());
+		if (it != s.end())
+			*it = x;
+		else
+			s.push_back(x);
+	}
+	std::cout << s.size() << std::endl;
+}
+
+#endif
diff --git a/02_sorting_and_searching/concert_tickets_1091.cpp b/02_sorting_and_searching/concert_tickets_1091.cpp
new file mode 100644
index 0000000..20333a6
--- /dev/null
+++ b/02_sorting_and_searching/concert_tickets_1091.cpp
@@ -0,0 +1,25 @@
+#include <algorithm>
+#include <iostream>
+#include <set>
+#include <vector>
+
+int main() {
+	size_t n, m;
+	std::cin >> n >> m;
+	std::vector<int> hv(n), t(m);
+	for (size_t i = 0; i < n; i++)
+		std::cin >> hv[i];
+	for (size_t i = 0; i < m; i++)
+		std::cin >> t[i];
+
+	std::multiset<int, std::greater<int>> h(hv.begin(), hv.end());
+
+	for (auto c : t) {
+		if (auto x = h.lower_bound(c); x == h.end()) {
+			std::cout << "-1\n";
+		} else {
+			std::cout << *x << "\n";
+			h.erase(x);
+		}
+	}
+}
diff --git a/02_sorting_and_searching/distinct_numbers_1621.cpp b/02_sorting_and_searching/distinct_numbers_1621.cpp
new file mode 100644
index 0000000..9c39aa3
--- /dev/null
+++ b/02_sorting_and_searching/distinct_numbers_1621.cpp
@@ -0,0 +1,13 @@
+#include <iostream>
+#include <set>
+
+int main() {
+	int n, x;
+	std::set<int> s;
+	std::cin >> n;
+	for (int i = 0; i < n; i++) {
+		std::cin >> x;
+		s.insert(x);
+	}
+	std::cout << s.size() << "\n";
+}
diff --git a/02_sorting_and_searching/ferris_wheel_1090.cpp b/02_sorting_and_searching/ferris_wheel_1090.cpp
new file mode 100644
index 0000000..f64b33b
--- /dev/null
+++ b/02_sorting_and_searching/ferris_wheel_1090.cpp
@@ -0,0 +1,17 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	int n, x;
+	std::cin >> n >> x;
+	std::vector<int> a(n);
+	for (int i = 0; i < n; i++)
+		std::cin >> a[i];
+	std::sort(a.begin(), a.end());
+	size_t i{0}, j{a.size()-1}, s{0};
+	for (; j > i; j--, s++)
+		i += a[i] + a[j] <= x;
+	if (i == j) s++;
+	std::cout << s << "\n";
+}
diff --git a/02_sorting_and_searching/maximum_subarray_sum_1643.cpp b/02_sorting_and_searching/maximum_subarray_sum_1643.cpp
new file mode 100644
index 0000000..24ac320
--- /dev/null
+++ b/02_sorting_and_searching/maximum_subarray_sum_1643.cpp
@@ -0,0 +1,19 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	size_t n;
+	std::cin >> n;
+	std::vector<long long> a(n);
+	for (size_t i = 0; i < n; i++)
+		std::cin >> a[i];
+
+	long long scur{0}, smax{0};
+	for (size_t j = 0; j < n; j++) {
+		scur = std::max(0LL, scur + a[j]);
+		smax = std::max(smax, scur);
+	}
+	if (smax == 0) smax = *std::max_element(a.begin(), a.end());
+	std::cout << smax << "\n";
+}
diff --git a/02_sorting_and_searching/missing_coin_sum_2183.cpp b/02_sorting_and_searching/missing_coin_sum_2183.cpp
new file mode 100644
index 0000000..ed7a74b
--- /dev/null
+++ b/02_sorting_and_searching/missing_coin_sum_2183.cpp
@@ -0,0 +1,16 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	size_t n, s{1};
+	std::cin >> n;
+	std::vector<size_t> a(n);
+	for (size_t i = 0; i < n; i++)
+		std::cin >> a[i];
+	std::sort(a.begin(), a.end());
+	for (auto c : a)
+		if (s < c) break;
+		else s+= c;
+	std::cout << s << std::endl;
+}
diff --git a/02_sorting_and_searching/movie_festival_1629.cpp b/02_sorting_and_searching/movie_festival_1629.cpp
new file mode 100644
index 0000000..4ec1fca
--- /dev/null
+++ b/02_sorting_and_searching/movie_festival_1629.cpp
@@ -0,0 +1,21 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	size_t n;
+	std::cin >> n;
+	std::vector<std::pair<int, int>> v(n);
+	for (size_t i = 0; i < n; i++)
+		std::cin >> v[i].first >> v[i].second;
+	std::sort(v.begin(), v.end());
+	int e{-1}, s{0};
+	for (auto a : v) {
+		if (a.first >= e) {
+			e = a.second;
+			s++;
+		}
+		e = std::min(e, a.second);
+	}
+	std::cout << s << "\n";
+}
diff --git a/02_sorting_and_searching/playlist_1141.cpp b/02_sorting_and_searching/playlist_1141.cpp
new file mode 100644
index 0000000..ff963f7
--- /dev/null
+++ b/02_sorting_and_searching/playlist_1141.cpp
@@ -0,0 +1,22 @@
+#include <algorithm>
+#include <iostream>
+#include <map>
+#include <vector>
+
+int main() {
+	size_t n;
+	std::cin >> n;
+	std::vector<int> v(n);
+	for (size_t i = 0; i < n; i++)
+		std::cin >> v[i];
+
+	size_t l{0}, s{0};
+	std::map<int, size_t> m;
+	for (size_t r = 0; r < n; r++) {
+		if (m.contains(v[r]))
+			l = std::max(l, m.at(v[r])+1);
+		m[v[r]] = r;
+		s = std::max(s, r-l+1);
+	}
+	std::cout << s << "\n";
+}
diff --git a/02_sorting_and_searching/restaurant_customers_1619.cpp b/02_sorting_and_searching/restaurant_customers_1619.cpp
new file mode 100644
index 0000000..8d97e96
--- /dev/null
+++ b/02_sorting_and_searching/restaurant_customers_1619.cpp
@@ -0,0 +1,24 @@
+#include <algorithm>
+#include <iostream>
+#include <queue>
+#include <vector>
+
+int main() {
+	size_t n;
+	std::cin >> n;
+	std::vector<std::pair<int, int>> c(n);
+	for (size_t i = 0; i < n; i++) {
+		int a, b;
+		std::cin >> a >> b;
+		c[i] = {a, b};
+	}
+	std::sort(c.begin(), c.end());
+	std::priority_queue<int, std::vector<int>, std::greater<int>> q;
+	size_t m{0};
+	for (auto d : c) {
+		while (!q.empty() && q.top() < d.first) q.pop();
+		q.push(d.second);
+		m = std::max(m, q.size());
+	}
+	std::cout << m << "\n";
+}
diff --git a/02_sorting_and_searching/room_allocation_1164.cpp b/02_sorting_and_searching/room_allocation_1164.cpp
new file mode 100644
index 0000000..f79cc96
--- /dev/null
+++ b/02_sorting_and_searching/room_allocation_1164.cpp
@@ -0,0 +1,38 @@
+#include <algorithm>
+#include <iostream>
+#include <queue>
+#include <tuple>
+#include <vector>
+
+int main() {
+	int n;
+	std::vector<std::tuple<int, int, int>> v;
+	std::cin >> n;
+	for (int i = 0; i < n; i++) {
+		int a, b;
+		std::cin >> a >> b;
+		v.push_back({a, b, i});
+	}
+	std::sort(v.begin(), v.end());
+
+	using P = std::pair<int, int>;
+	std::priority_queue<P, std::vector<P>, std::greater<>> r;
+	std::vector<int> al(n);
+	for (auto [a, d, i] : v) {
+		int ind = r.size()+1;
+		if (!r.empty()) {
+			auto [x, j] = r.top();
+			if (a > x) {
+				r.pop();
+				ind = j;
+			}
+		}
+		r.push({d, ind});
+		al[i] = ind;
+	}
+
+	std::cout << r.size() << "\n";
+	for (auto i : al)
+		std::cout << i << " ";
+	std::cout << "\n";
+}
diff --git a/02_sorting_and_searching/stick_lengths_1074.cpp b/02_sorting_and_searching/stick_lengths_1074.cpp
new file mode 100644
index 0000000..e41a7d8
--- /dev/null
+++ b/02_sorting_and_searching/stick_lengths_1074.cpp
@@ -0,0 +1,16 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	long long n;
+	std::cin >> n;
+	std::vector<long long> a(n);
+	for (long long i = 0; i < n; i++)
+		std::cin >> a[i];
+	std::sort(a.begin(), a.end());
+	long long s{0}, t{a[n/2]};
+	for (auto x : a)
+		s += std::abs(x-t);
+	std::cout << s << "\n";
+}
diff --git a/02_sorting_and_searching/sum_of_two_values_1640.cpp b/02_sorting_and_searching/sum_of_two_values_1640.cpp
new file mode 100644
index 0000000..75b0f54
--- /dev/null
+++ b/02_sorting_and_searching/sum_of_two_values_1640.cpp
@@ -0,0 +1,27 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	int n, x;
+	std::cin >> n >> x;
+	std::vector<std::pair<int, int>> a(n);
+	for (int i = 0; i < n; i++) {
+		std::cin >> a[i].first;
+		a[i].second = i;
+	}
+	std::sort(a.begin(), a.end());
+
+	int i{0}, j{n-1};
+	while (i < j) {
+		auto [ai, ii] = a[i];
+		auto [aj, ij] = a[j];
+		if (ai + aj < x) i++;
+		else if (ai + aj > x) j--;
+		else {
+			std::cout << ii+1 << " " << ij+1 << "\n";
+			return 0;
+		}
+	}
+	std::cout << "IMPOSSIBLE\n";
+}
diff --git a/02_sorting_and_searching/towers_1063.cpp b/02_sorting_and_searching/towers_1063.cpp
new file mode 100644
index 0000000..b0656f3
--- /dev/null
+++ b/02_sorting_and_searching/towers_1063.cpp
@@ -0,0 +1,17 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+
+int main() {
+	size_t n;
+	std::cin >> n;
+	std::vector<int> v;
+	for (size_t i = 0; i < n; i++) {
+		int x;
+		std::cin >> x;
+		auto it = std::upper_bound(v.begin(), v.end(), x);
+		if (it == v.end()) v.push_back(x);
+		else *it = x;
+	}
+	std::cout << v.size() << "\n";
+}
-- 
cgit v1.3