CSES - Shared codeLink to this code:
https://cses.fi/paste/9e806894689f8489283d05/
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<pair<int,int>> pairs;
vector<int> tmp;
while(n--){
int x,y; cin >> x >> y;
pairs.push_back(make_pair(x,y));
tmp.push_back(x);
tmp.push_back(y);
}
sort(tmp.begin(),tmp.end());
vector<int> unique;
unique.push_back(tmp[0]);
for(int i=1;i<tmp.size();i++){
if(tmp[i] != unique.back())
unique.push_back(tmp[i]);
}
unordered_map<int,int> forwardMap;
int j = 0;
for(auto i=unique.begin();i!=unique.end();i++,j++){
forwardMap[*i] = j;
}
vector<int> mins(j,j+1);
vector<int> maxs(j,0);
vector<int> maxUpTo(j,0);
for(int i=0;i<pairs.size();i++){
int L = forwardMap[pairs[i].first];
int R = forwardMap[pairs[i].second];
mins[L] = min(mins[L],R);
maxs[L] = max(maxs[L],R);
}
for(int i=0;i<maxs.size()-1;i++){
maxUpTo[i+1] = max(maxUpTo[i],maxs[i]);
}
const int MAXN = 400001;
const int K = 18;
int N = maxs.size();
int log[MAXN+1];
log[1] = 0;
for (int i = 2; i <= MAXN; i++)
log[i] = log[i/2] + 1;
int st[MAXN][K + 1];
for (int i = 0; i < N; i++)
st[i][0] = mins[i];
for (int j = 1; j <= K; j++)
for (int i = 0; i + (1 << j) <= N; i++)
st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
for(int i=0;i<pairs.size();i++){
int L = forwardMap[pairs[i].first]+1;
int R = forwardMap[pairs[i].second];
int j = log[R - L + 1];
int minimum = min(st[L][j], st[R - (1 << j) + 1][j]);
L--;
if(minimum <= R || (mins[L] < R))
cout << "1" << " ";
else
cout << "0" << " ";
}
cout << endl;
for(int i=0;i<pairs.size();i++){
int L = forwardMap[pairs[i].first];
int R = forwardMap[pairs[i].second];
int maximum = maxUpTo[L];
if(maximum >= R || maxs[L] > R)
cout << "1" << " ";
else
cout << "0" << " ";
}
cout << endl;
return 0;
}