cses

commit 7603c5611f62bfe104a423f8c9565add4506e40d
parent fb8240fb0274fd51dde578eb31bff8a6ee414f63
Author: superpozycja <anna@superpozycja.net>
Date:   Thu, 31 Oct 2024 20:41:17 +0100

solve nested ranges check

Diffstat:
A
sorting_and_searching/nested_ranges_check.cpp
 | 
90
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 90 insertions(+), 0 deletions(-)
diff --git a/sorting_and_searching/nested_ranges_check.cpp b/sorting_and_searching/nested_ranges_check.cpp
@@ -0,0 +1,90 @@
+#include <bits/stdc++.h>
+
+using namespace std;
+
+using ui = unsigned int;
+using l = long;
+using ul = unsigned long;
+using ll = long long;
+using ull = unsigned long long;
+
+using vi = vector<int>;
+using vui = vector<ui>;
+using vl = vector<l>;
+using vul = vector<ul>;
+using vll = vector<ll>;
+using vull = vector<ull>;
+
+void solve()
+{
+	int n;
+	cin >> n;
+	vector<
+		pair<
+			pair<int, int>,
+			pair<int, int>
+		>
+	> a;
+
+	for (int i = 0; i < n; i++) {
+		int t, t2;
+		cin >> t >> t2;
+		a.push_back({{t, t2}, {i, 0}});
+	}
+
+	sort(a.begin(), a.end(), 
+	     [](auto &l, auto &r) {
+	     	if (l.first.first == r.first.first)
+		     return l.first.second < r.first.second;
+		return l.first.first > r.first.first;
+	     });
+
+	int mr = INT_MAX;
+	for (auto &x : a) {
+		if (mr <= x.first.second)
+			x.second.second = 1;
+		mr = min(mr, x.first.second);
+	}
+	sort(a.begin(), a.end(), 
+	     [](auto &l, auto &r) {
+		return l.second.first < r.second.first;
+	     });
+
+	for (auto x : a) {
+		cout << x.second.second << " ";
+	}
+	cout << "\n";
+
+	sort(a.begin(), a.end(), 
+	     [](auto &l, auto &r) {
+	     	if (l.first.first == r.first.first)
+		     return l.first.second > r.first.second;
+		return l.first.first < r.first.first;
+	     });
+
+	mr = 0;
+	for (auto &x : a) {
+		x.second.second = 0;
+		if (mr >= x.first.second)
+			x.second.second = 1;
+		mr = max(mr, x.first.second);
+	}
+
+	sort(a.begin(), a.end(), 
+	     [](auto &l, auto &r) {
+		return l.second.first < r.second.first;
+	     });
+
+	for (auto x : a) {
+		cout << x.second.second << " ";
+	}
+	cout << "\n";
+
+}
+
+int main()
+{
+	ios::sync_with_stdio(0);
+	cin.tie(0);
+	solve();
+}