| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1013529 | spacewalker | Ideal city (IOI12_city) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}