#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1'000'000'000;
struct Segment {
int x, y1, y2;
Segment(int x, int y1, int y2) : x(x), y1(y1), y2(y2) {}
};
ostream& operator << (ostream& os, const Segment &s) {
return os << "[x = " << s.x << "; y = " << s.y1 << "..." << s.y2 << "]";
}
bool adjacent(const Segment &a, const Segment &b) {
return abs(a.x - b.x) <= 1 && max(a.y1, b.y1) <= min(a.y2, b.y2);
}
vector<Segment> divide_into_segments(const vector<pair<int, int>> &blocks) {
vector<Segment> segments;
optional<Segment> currentSegment;
for (int i = 0; i < blocks.size(); ++i) {
if (!currentSegment) currentSegment = Segment(blocks[i].first, blocks[i].second, blocks[i].second);
else if (currentSegment->x != blocks[i].first || currentSegment->y2 + 1 < blocks[i].second) {
segments.push_back(*currentSegment);
currentSegment = Segment(blocks[i].first, blocks[i].second, blocks[i].second);
} else {
currentSegment->y2 = blocks[i].second;
}
}
if (currentSegment) segments.push_back(*currentSegment);
return segments;
}
ll pair_distance_sum(const vector<ll> &points) {
if (points.size() == 0) {
return 0;
}
ll ans = 0;
ll total = accumulate(points.begin(), points.end(), 0LL);
ll right_side = 0;
for (int i = 0; i < points.size(); ++i) {
right_side += points[i];
ans += right_side * (total - right_side) % MOD;
}
/*
cerr << "PDS " << ans;
for (ll v : points) cerr << " " << v;
cerr << endl;
*/
return ans % MOD;
}
vector<vector<ll>> segments_reachable;
ll sum_of_distances(int n, const vector<vector<int>> &tree, const vector<Segment> &segs, int v, int p) {
auto cseg = segs[v];
int length = cseg.y2 - cseg.y1 + 1;
segments_reachable[v].assign(length, 1);
auto comp = [&] (int y) {
return clamp(y, cseg.y1, cseg.y2) - cseg.y1;
};
ll ans = 0;
for (int child : tree[v]) {
if (child == p) continue;
ans += sum_of_distances(n, tree, segs, child, v);
int comp_min = comp(segs[child].y1), comp_max = comp(segs[child].y2);
vector<ll> csubsegment(comp_max - comp_min + 1);
ll segments_in_child = accumulate(segments_reachable[child].begin(),
segments_reachable[child].end(), 0LL);
for (int y = segs[child].y1; y <= segs[child].y2; ++y) {
ll segments_here = segments_reachable[child][y - segs[child].y1];
segments_reachable[v][comp(y)] += segments_here;
csubsegment[comp(y) - comp_min] += segments_here;
ll delta_y = abs(y - clamp(y, cseg.y1, cseg.y2)) + 1;
ans += delta_y * segments_here % MOD * (n - segments_in_child) % MOD;
}
ans -= pair_distance_sum(csubsegment);
}
ans += pair_distance_sum(segments_reachable[v]);
ans = (ans % MOD + MOD) % MOD;
// cerr << "SOD " << v << " (par " << p << " " << segs[v] << ") ans " << ans << endl;
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
segments_reachable.assign(N, vector<ll>());
vector<pair<int, int>> blocks(N);
for (int i = 0; i < N; ++i) blocks[i] = {X[i], Y[i]};
sort(blocks.begin(), blocks.end());
auto segments = divide_into_segments(blocks);
// for (auto &s : segments) cerr << s << endl;
int k = segments.size();
vector<vector<int>> tree(k);
for (int i = 0, j = 0, prev = 0; i < k; prev = i, i = j) {
while (j < k && segments[j].x == segments[i].x) ++j;
int cprev = prev;
for (int cseg_i = i; cseg_i < j; ++cseg_i) {
while (cprev < i && segments[cprev].y2 < segments[cseg_i].y1) ++cprev;
while (cprev < i && adjacent(segments[cseg_i], segments[cprev])) {
// cerr << "adjacent " << segments[cseg_i] << " " << segments[cprev] << endl;
tree[cseg_i].push_back(cprev);
tree[cprev].push_back(cseg_i);
if (segments[cprev].y2 <= segments[cseg_i].y1) {
++cprev;
} else {
break;
}
}
}
}
return sum_of_distances(N, tree, segments, 0, -1);
}
Compilation message
city.cpp: In function 'std::vector<Segment> divide_into_segments(const std::vector<std::pair<int, int> >&)':
city.cpp:23:3: error: 'optional' was not declared in this scope
23 | optional<Segment> currentSegment;
| ^~~~~~~~
city.cpp:23:3: note: 'std::optional' is only available from C++17 onwards
city.cpp:23:19: error: expected primary-expression before '>' token
23 | optional<Segment> currentSegment;
| ^
city.cpp:23:21: error: 'currentSegment' was not declared in this scope
23 | optional<Segment> currentSegment;
| ^~~~~~~~~~~~~~
city.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i = 0; i < blocks.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
city.cpp: In function 'll pair_distance_sum(const std::vector<long long int>&)':
city.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for (int i = 0; i < points.size(); ++i) {
| ~~^~~~~~~~~~~~~~~
city.cpp: In lambda function:
city.cpp:64:12: error: 'clamp' was not declared in this scope
64 | return clamp(y, cseg.y1, cseg.y2) - cseg.y1;
| ^~~~~
city.cpp: In function 'll sum_of_distances(int, const std::vector<std::vector<int> >&, const std::vector<Segment>&, int, int)':
city.cpp:72:28: error: 'comp_max' was not declared in this scope; did you mean 'comp_min'?
72 | vector<ll> csubsegment(comp_max - comp_min + 1);
| ^~~~~~~~
| comp_min
city.cpp:80:28: error: 'clamp' was not declared in this scope
80 | ll delta_y = abs(y - clamp(y, cseg.y1, cseg.y2)) + 1;
| ^~~~~
