Link 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;
}