# Untitled

unknown
plain_text
a year ago
2.6 kB
31
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 ap=v.cmp;
int da=v.dmp;
for(auto &index:v.t)
{
}
}

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();
// }
}```