Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
2.6 kB
28
Indexable
Never
#include <bits/stdc++.h>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define l1 long long
// #define int long long
using pi=pair<int,int>;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
typedef tree<pair<int, int>, null_type,
             less<pair<int, int> >, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

struct ranges
{
	pi ran;
	vector<int>t;
	int cmp;
	int dmp;
};
 
void solve()
{
    int n;
	cin>>n;
 
	vector<pair<pi,int>>a(n);
	// map<pi,int>cmp;
	// map<pi,int>dmp;
	// map<pi,vector<int>>in;
	unordered_map<int,int>mpl;
	unordered_map<int,int>mpc;
	// map<pi,int>mpn;
	for(int i=0;i<n;i++)
	{
		cin>>a[i].ff.ff>>a[i].ff.ss;
		a[i].ss=i;
		// in[a[i].ff].push_back(i);
		// mpn[a[i].ff]++;
	}
	vector<struct ranges>mplv;
	sort(a.begin(),a.end());
	for(int i=0;i<a.size();i++)
	{
		if(mplv.size()==0)
		{
			struct ranges tmp;
			tmp.ran=a[i].ff;
			tmp.t.push_back(a[i].ss);
			mplv.push_back(tmp);
		}
		else
		{
			if(a[i].ff==mplv.back().ran)
			{
				mplv.back().t.push_back(a[i].ss);
			}
			else
			{
				struct ranges tmp;
				tmp.ran=a[i].ff;
				tmp.t.push_back(a[i].ss);
				mplv.push_back(tmp);
			}
		}
	}

 
	
 
	ordered_set pre;
	ordered_set suf;
 
	int jk=0;
	// vector<struct ranges>mplv;
	for(auto &v:mplv)
	{
		suf.insert({v.ran.second,jk++});
		mpl[v.ran.ff]+=v.t.size();
	}
 
 
	auto it=mplv.begin();
	auto ind=it->ran;
	suf.erase({ind.ss,0});
	it->dmp=mpl[ind.ff]-it->t.size();
	mpl[ind.ff]-=it->t.size();
	mpc[ind.ff]+=it->t.size();
	it->cmp=suf.order_of_key({ind.ss+1,0});
	pre.insert({ind.ss,0});
 
	for(int i=1;i<jk;i++)
	{
		it++;
		ind=it->ran;
		suf.erase({ind.ss,i});
		int dmp_ind=0,cmp_ind=0;
		int &mpl_ind=mpl[ind.ff];
		int &mpc_ind=mpc[ind.ff];
		dmp_ind=pre.size()-pre.order_of_key({ind.ss,-1});
		mpl_ind-=it->t.size();
		dmp_ind+=mpl_ind;
		cmp_ind+=mpc_ind;
		mpc_ind+=it->t.size();
		cmp_ind+=suf.order_of_key({ind.ss+1,0});
		pre.insert({ind.ss,i});
		it->dmp=dmp_ind;
		it->cmp=cmp_ind;
	}
 
	vector<int>c(n);
	vector<int>d(n);
 
	
	for(auto &v:mplv)
	{
		int ad=v.t.size();
		int ap=v.cmp;
		int da=v.dmp;
		for(auto &index:v.t)
		{
			c[index]=ap+ad-1;
			d[index]=da+ad-1;
		}
	}
 
	
 
 
 
 
 
		for(int i=0;i<n;i++)
		cout<<c[i]<<" ";
		cout<<"\n";
		for(int i=0;i<n;i++)
		cout<<d[i]<<" ";
 
 
	
 
 
	
 
	
	
 
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // int t;
    // cin>>t;
    // while(t--)
    // {
        solve();
    // }
}