#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100001];
long long sz[100001];
long long n;
long long all = 0;
long long mod = 1000000000;
void dfs(int i,int pr){
for(auto j:adj[i]){
if(j==pr)continue;
dfs(j,i);
all+=(sz[j]*(n-sz[j]))%mod;
all%=mod;
sz[i]+=sz[j];
}
}
void calc(vector<int> X,vector<int> Y){
map<pair<int,int>,int> mp,ed;
vector<pair<int,int>> v;
for(int i =0;i<n;i++){
v.push_back({X[i],Y[i]});
}
sort(v.begin(),v.end());
for(int i = 0;i<n;i++){
mp[{v[i].first,v[i].second}] = i+1;
}
int ans[n];int nod = 0;
for(int i = 0;i<n;i++){
if(i&&v[i].first==v[i-1].first&&v[i-1].second+1==v[i].second){
ans[i] = ans[i-1];
}else {
adj[nod].clear();
sz[nod] = 0;
ans[i] = nod++;
}
sz[ans[i]]++;
int lol = mp[{v[i].first-1,v[i].second}];
if(lol&&ed[{ans[i],ans[lol-1]}]==0){
ed[{ans[i],ans[lol-1]}] = 1;
ed[{ans[lol-1],ans[i]}] = 1;
adj[ans[i]].push_back(ans[lol-1]);
adj[ans[lol-1]].push_back(ans[i]);
}
}
dfs(0,-1);
}
int DistanceSum(int N,vector<int> X,vector<int> Y){
all = 0;
n = N;
calc(X,Y);
calc(Y,X);
return all;
}
/*int main(){
//ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cout<<DistanceSum(11,{2,2,3,3,4,4,4,4,5,5,5},{5,6,3,6,3,4,5,6,3,4,6});
}*/
Compilation message
/usr/bin/ld: /tmp/cc64fCmg.o: in function `main':
grader.cpp:(.text.startup+0x104): undefined reference to `DistanceSum(int, int*, int*)'
collect2: error: ld returned 1 exit status
