#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define S second
#define F first
#define pii pair<ll,ll>
#define vi vector <ll>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000000
#define MAXN 1000000
using namespace std;
vvi adj(MAXN+1);
vi a(MAXN+1);
ll ans=0;
int n;
void dfs(ll v,ll p){
for (int to:adj[v]){
if (to==p)continue;
dfs(to,v);
a[v]+=a[to];
}
ans=(ans+(a[v]*(n-a[v]))%MOD)%MOD;
}
int DistanceSum(int N, int X[], int Y[]){
n=N;
vp arr;
map <pii,ll> m;
for (ll i=0;i<N;i++)arr.pb({1ll*X[i],1ll*Y[i]});
sort(arr.begin(),arr.end());
ll cnt=0;
ll sz=0;
for (auto &[x,y]:arr){
if (!m[{x,y-1}]){
a[cnt]=sz;
cnt++;
sz=1;
if (m[{x-1,y}]){
adj[cnt].pb(m[{x-1,y}]);
adj[m[{x-1,y}]].pb(cnt);
}
}else{
sz++;
if (m[{x-1,y}] && !m[{x-1,y-1}]){
adj[cnt].pb(m[{x-1,y}]);
adj[m[{x-1,y}]].pb(cnt);
}
}
m[{x,y}]=cnt;
}
a[cnt]=sz;
dfs(1,0);
arr.clear();
m.clear();
cnt=sz=0;
adj.assign(MAXN+1,{});
a.assign(MAXN+1,0);
for (ll i=0;i<N;i++)arr.pb({1ll*Y[i],1ll*X[i]});
sort(arr.begin(),arr.end());
for (auto &[y,x]:arr){
if (!m[{x-1,y}]){
a[cnt]=sz;
cnt++;
sz=1;
if (m[{x,y-1}]){
adj[cnt].pb(m[{x,y-1}]);
adj[m[{x,y-1}]].pb(cnt);
}
}else{
sz++;
if (m[{x,y-1}] && !m[{x-1,y-1}]){
adj[cnt].pb(m[{x,y-1}]);
adj[m[{x,y-1}]].pb(cnt);
}
}
m[{x,y}]=cnt;
}
a[cnt]=sz;
dfs(1,0);
return ans;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
int n;
cin>>n;
int x[n],y[n];
for (int i=0;i<n;i++)cin>>x[i]>>y[i];
cout<<DistanceSum(n,x,y);
}
Compilation message
/usr/bin/ld: /tmp/ccnZRSro.o: in function `main':
city.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3mIlcq.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
