#include <bits/stdc++.h>
using namespace std;
#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const ll inf = 2e9;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
ii intersect(ii a, ii b) {
return ii(max(a.F, b.F), min(a.S, b.S));
}
#define get(x,y) (lower_bound(all(a),ii(x,y))-a.begin())
int DistanceSum(int N, int *X, int *Y) {
int n = N;
vector<ii> a(n);
FOR (i, 0, n - 1) {
a[i] = ii(X[i], Y[i]);
}
sort(all(a));
map<ii, int> no;
vector<ii> sg;
vector<vi> t(n);
FOR (i, 0, n - 1) {
int x = a[i].F, y = a[i].S;
int j = i;
while (j+1 < n and a[j+1].F == x and a[j+1].S == a[j].S+1) ++j;
FOR (it, i, j) no[a[it]] = sz(sg);
FOR (it, i, j) {
ii cur(a[it].F-1,a[it].S);
if (no.count(cur)) {
t[sz(sg)].emplace_back(no[cur]);
t[no[cur]].emplace_back(sz(sg));
}
}
sg.emplace_back(i, j);
i = j;
}
FOR (i, 0, n - 1) {
sort(all(t[i])); t[i].erase(unique(all(t[i])), t[i].end());
}
// pr(t);
ll ans = 0;
vector<ll> down(n), up(n), same(n);
vector<ll> downC(n), upC(n), sameC(n);
function<void(int,int)> dfsD = [&](int u, int par) {
for (int v: t[u]) if (v != par) dfsD(v, u);
int i = sg[u].F, j = sg[u].S;
int x = a[i].F, y1 = a[i].S, y2 = a[j].S;
int l = 0, r = j-i;
// pr(t);
FOR (it, i, j) {
int y = a[it].S;
sameC[it] = l + r + 1;
same[it] = (r*(r+1LL)/2 + l*(l+1LL)/2) % inf;
++l, --r;
for (int v: t[u]) if (v != par) {
ii pt = intersect(ii(y1, y2), ii(a[sg[v].F].S, a[sg[v].S].S));
int ptr = -1;
if (y >= pt.F and y <= pt.S) ptr = get(a[sg[v].F].F, y);
else if (abs(y-pt.F) < abs(y-pt.S)) ptr = get(a[sg[v].F].F, pt.F);
else ptr = get(a[sg[v].F].F, pt.S);
ll d = 1 + abs(y - a[ptr].S);
// pr(a[it],a[ptr]);
// pr(a[it],v,d);
downC[it] += downC[ptr] + sameC[ptr];
down[it] = (down[it] + d * downC[ptr] + down[ptr]) % inf;
down[it] = (down[it] + d * sameC[ptr] + same[ptr]) % inf;
}
// pr(a[it], down[it]);
}
};
function<void(int,int)> dfsU = [&](int u, int par) {
int i = sg[u].F, j = sg[u].S;
int x = a[i].F, y1 = a[i].S, y2 = a[j].S;
FOR (it, i, j) if (par>=0) {
int y = a[it].S;
int v = par;
ii pt = intersect(ii(y1, y2), ii(a[sg[v].F].S, a[sg[v].S].S));
int ptr = -1;
if (y >= pt.F and y <= pt.S) ptr = get(a[sg[v].F].F, y);
else if (abs(y-pt.F) < abs(y-pt.S)) ptr = get(a[sg[v].F].F, pt.F);
else ptr = get(a[sg[v].F].F, pt.S);
ll d = 1 + abs(y - a[ptr].S);
upC[it] += upC[ptr] + sameC[ptr];
upC[it] += downC[ptr] - downC[it] - sameC[it];
up[it] = (up[it] + d*upC[ptr] + up[ptr] + same[ptr] + d*sameC[ptr]) % inf;
up[it] = (up[it] + d*downC[ptr] + down[ptr]) % inf;
int o = get(x,a[ptr].S);
// pr(a[it], par, a[ptr], a[o]);
up[it] = (up[it] - (d+1)*downC[o] - down[o])%inf;
up[it] = (up[it] - (d+1)*sameC[o] - same[o])%inf;
if (up[it] < 0) up[it] += inf;
// pr(a[it], a[ptr], upC[it]);
}
for (int v: t[u]) if (v != par) dfsU(v, u);
};
dfsD(0, -1);
dfsU(0, -1);
FOR (i, 0, n - 1) ans = (ans + up[i] + down[i] + same[i]) % inf;
return ans/2;
}
int main() {
int n; cin >> n;
vi x(n), y(n);
FOR (i, 0, n - 1)cin >> x[i] >> y[i];
cout << DistanceSum(n, &x[0], &y[0]) << "\n";
}
Compilation message
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:42:19: warning: unused variable 'y' [-Wunused-variable]
int x = a[i].F, y = a[i].S;
^
city.cpp: In lambda function:
city.cpp:68:7: warning: unused variable 'x' [-Wunused-variable]
int x = a[i].F, y1 = a[i].S, y2 = a[j].S;
^
/tmp/ccuf7naa.o: In function `main':
city.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccsRZBV7.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
