#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
const int N=1e5+5;
const int mod=1e9;
int s[N],ans,n,cnt,X[N],Y[N];
pair<int,int>a[N];
map<pair<int,int>,int>mp;
vector<int>V[N],v[N];
void dfs(int u,int p){
s[u]=v[u].back()-v[u][0]+1; s[u]%=mod;
for(int i=0;i<V[u].size();i++){
if(V[u][i]!=p){
dfs(V[u][i],u);
s[u]+=s[V[u][i]];
s[u]%=mod;
}
}
ans+=s[u]*(n-s[u])%mod;//cout<<u<<" -- "<<s[u]<<endl;
ans%=mod;
}
void Tree(){
//cout<<"+"<<endl;
for(int i=0;i<n;i++){
if(!i || a[i].f!=a[i-1].f || a[i].s!=a[i-1].s+1){
cnt++;
//cout<<a[i].f<<" "<<a[i].s<<"_"<<cnt<<endl;
} mp[{a[i].f,a[i].s}]=cnt;v[cnt].push_back(a[i].s);
}
for(int i=0;i<n;i++){
if(mp[{a[i].f+1,a[i].s}]){
int cc=mp[{a[i].f+1,a[i].s}];
if(V[mp[{a[i].f,a[i].s}]].size()==0 || V[mp[{a[i].f,a[i].s}]].back()!=cc){
V[mp[{a[i].f,a[i].s}]].push_back(cc);
V[cc].push_back(mp[{a[i].f,a[i].s}]);
}
}
}
dfs(1,0);
}
int DistanceSum(int N, int *X, int *Y) {
for(int i=0;i<N;i++){
a[i]={X[i],Y[i]};
} n=N;
sort(a,a+N);
Tree();
for(int i=1;i<=cnt;i++)
v[i].clear(),V[i].clear();
cnt=0;
for(int i=0;i<N;i++)
mp[{a[i].f,a[i].s}]=0,swap(a[i].f,a[i].s);
sort(a,a+N);
Tree();
return ans;
}
Compilation message
city.cpp: In function 'void dfs(long long int, long long int)':
city.cpp:14:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i=0;i<V[u].size();i++){
| ~^~~~~~~~~~~~
/tmp/ccEVUsb6.o: In function `main':
grader.cpp:(.text.startup+0xff): undefined reference to `DistanceSum(int, int*, int*)'
collect2: error: ld returned 1 exit status
