#### FIX:↵
Turned the indexed set into an indexed **multi**set, as there can be multiple equal R ranges. This can be done by changing the template to `template <typename T>↵
using indexed_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;` (changing `less` to `less_equal`).↵
↵
### Problem Statement↵
↵
Given n ranges, your task is to count for each range how many other ranges it contains and how many other ranges contain it.↵
↵
### My approach↵
↵
Insert all ranges into a vector and sort it. Iterating through it, a given range contains all of those to its left with the same left boundary, since their right boundary will also be smaller than the current's. So we do a lowerbound in the vector and get all of them. The given range also contains all of those to its right (bigger left boundaries) whose right boundary is smaller than the current. So I just iterate from right to left in the sorted vector keeping an indexed set to get how many elements to my right have a smaller right boundary. I add these two results to an answer vector.↵
↵
For the contained task, the approach is similar; just add the number of ranges with the same left boundary and bigger right boundary, also those to its left with bigger right boundary.↵
↵
Is my approach wrong? I don't understand why my code nets wrong answer. The tests in which it occurs are too big for me to debug.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
#define int long long↵
#define endl "\n"↵
using namespace std;↵
using namespace __gnu_pbds;↵
template <typename T>↵
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
void solve(){↵
int n;↵
cin >> n;↵
vector<pair<int, int>>ranges(n);↵
vector<pair<pair<int, int>, int>>sorted_rangesL(n);↵
vector<int>contains(n), contained(n);↵
for (int i = 0; i < n; i++){↵
int x, y;↵
cin >> x >> y;↵
ranges[i] = {x, y};↵
sorted_rangesL[i] = {{x, y}, i};↵
}↵
↵
↵
sort(sorted_rangesL.begin(), sorted_rangesL.end());↵
indexed_set<int>right_window;↵
for (int i = n - 1; i >= 0; i--) {↵
int L = sorted_rangesL[i].first.first;↵
int R = sorted_rangesL[i].first.second;↵
int index = sorted_rangesL[i].second;↵
↵
// Compute position of first range with the same L but smaller R↵
int pos = i - (lower_bound(sorted_rangesL.begin(), sorted_rangesL.begin() + i, make_pair(make_pair(L, -1ll), -1ll)) - sorted_rangesL.begin());↵
↵
// Find count of ranges in right_window with R <= current R↵
int count = right_window.order_of_key(R + 1); // Count of elements <= R↵
↵
// Total ranges contained by the current range↵
contains[index] = pos + count;↵
↵
// Add the current range's R to the right_window↵
right_window.insert(R);↵
}↵
↵
↵
indexed_set<int>left_window;↵
for (int i = 0; i < n; i++){↵
int L = sorted_rangesL[i].first.first;↵
int R = sorted_rangesL[i].first.second;↵
int index = sorted_rangesL[i].second;↵
↵
// Compute position of last range with the same L but greater R↵
int pos = (lower_bound(sorted_rangesL.begin() + i, sorted_rangesL.end(), make_pair(make_pair(L + 1ll, -1ll), -1ll)) - sorted_rangesL.begin()) - i - 1;↵
↵
// Find count of ranges in left_window with R >= current R↵
int count = left_window.size() - left_window.order_of_key(R); // Count of elements >= R↵
↵
// Total ranges containing by the current range↵
contained[index] = pos + count;↵
↵
// Add the current range's R to the left_window↵
left_window.insert(R);↵
}↵
↵
for (int i = 0; i < n; i++)↵
cout << contains[i] << " \n"[i + 1 == n];↵
↵
for (int i = 0; i < n; i++)↵
cout << contained[i] << " \n"[i + 1 == n];↵
↵
}↵
↵
signed main(){↵
#ifndef ONLINE_JUDGE↵
freopen("input.in","r",stdin);↵
freopen("output.out","w",stdout);↵
#endif↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
// int t; cin >> t; while (t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
Turned the indexed set into an indexed **multi**set, as there can be multiple equal R ranges. This can be done by changing the template to `template <typename T>↵
using indexed_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;` (changing `less` to `less_equal`).↵
↵
### Problem Statement↵
↵
Given n ranges, your task is to count for each range how many other ranges it contains and how many other ranges contain it.↵
↵
### My approach↵
↵
Insert all ranges into a vector and sort it. Iterating through it, a given range contains all of those to its left with the same left boundary, since their right boundary will also be smaller than the current's. So we do a lowerbound in the vector and get all of them. The given range also contains all of those to its right (bigger left boundaries) whose right boundary is smaller than the current. So I just iterate from right to left in the sorted vector keeping an indexed set to get how many elements to my right have a smaller right boundary. I add these two results to an answer vector.↵
↵
For the contained task, the approach is similar; just add the number of ranges with the same left boundary and bigger right boundary, also those to its left with bigger right boundary.↵
↵
Is my approach wrong? I don't understand why my code nets wrong answer. The tests in which it occurs are too big for me to debug.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
#define int long long↵
#define endl "\n"↵
using namespace std;↵
using namespace __gnu_pbds;↵
template <typename T>↵
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
void solve(){↵
int n;↵
cin >> n;↵
vector<pair<int, int>>ranges(n);↵
vector<pair<pair<int, int>, int>>sorted_rangesL(n);↵
vector<int>contains(n), contained(n);↵
for (int i = 0; i < n; i++){↵
int x, y;↵
cin >> x >> y;↵
ranges[i] = {x, y};↵
sorted_rangesL[i] = {{x, y}, i};↵
}↵
↵
↵
sort(sorted_rangesL.begin(), sorted_rangesL.end());↵
indexed_set<int>right_window;↵
for (int i = n - 1; i >= 0; i--) {↵
int L = sorted_rangesL[i].first.first;↵
int R = sorted_rangesL[i].first.second;↵
int index = sorted_rangesL[i].second;↵
↵
// Compute position of first range with the same L but smaller R↵
int pos = i - (lower_bound(sorted_rangesL.begin(), sorted_rangesL.begin() + i, make_pair(make_pair(L, -1ll), -1ll)) - sorted_rangesL.begin());↵
↵
// Find count of ranges in right_window with R <= current R↵
int count = right_window.order_of_key(R + 1); // Count of elements <= R↵
↵
// Total ranges contained by the current range↵
contains[index] = pos + count;↵
↵
// Add the current range's R to the right_window↵
right_window.insert(R);↵
}↵
↵
↵
indexed_set<int>left_window;↵
for (int i = 0; i < n; i++){↵
int L = sorted_rangesL[i].first.first;↵
int R = sorted_rangesL[i].first.second;↵
int index = sorted_rangesL[i].second;↵
↵
// Compute position of last range with the same L but greater R↵
int pos = (lower_bound(sorted_rangesL.begin() + i, sorted_rangesL.end(), make_pair(make_pair(L + 1ll, -1ll), -1ll)) - sorted_rangesL.begin()) - i - 1;↵
↵
// Find count of ranges in left_window with R >= current R↵
int count = left_window.size() - left_window.order_of_key(R); // Count of elements >= R↵
↵
// Total ranges containing by the current range↵
contained[index] = pos + count;↵
↵
// Add the current range's R to the left_window↵
left_window.insert(R);↵
}↵
↵
for (int i = 0; i < n; i++)↵
cout << contains[i] << " \n"[i + 1 == n];↵
↵
for (int i = 0; i < n; i++)↵
cout << contained[i] << " \n"[i + 1 == n];↵
↵
}↵
↵
signed main(){↵
#ifndef ONLINE_JUDGE↵
freopen("input.in","r",stdin);↵
freopen("output.out","w",stdout);↵
#endif↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
// int t; cin >> t; while (t--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
