#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int) 1e5 + 7;
const int M = (int) 1e9;
int add(int a, int b) {
a += b;
if (a >= M) a -= M;
if (a < 0) a -= M;
return a;
}
int mul(int a, int b) {
return a * (ll) b % M;
}
void addup(int &a, int b) {
a = add(a, b);
}
void mulup(int a, int b) {
a = a * (ll) b % M;
}
class Segment {
private:
public:
int l, r, id;
Segment(int l, int r, int id) :
l(l),
r(r),
id(id) {
}
};
vector<int> g[N];
vector<Segment> segs[N];
void addEdge(int a, int b) {
g[a].push_back(b);
g[b].push_back(a);
}
int sum[N], T;
void dfs1(int a, int p = -1) {
for (auto &b : g[a]) {
if (b == p) continue;
dfs1(b, a);
sum[a] += sum[b];
}
}
void dfs2(int &sol, int a, int p = -1) {
for (auto &b : g[a]) {
if (b == p) continue;
dfs2(sol, b, a);
addup(sol, mul(sum[b], T - sum[b]));
}
}
int compute(int n, int *x, int *y) {
T = n;
int sol = 0;
for (int i = 0; i < n; i++) g[i].clear(), segs[i].clear();
for (int i = 0; i < n; i++) g[x[i]].push_back(y[i]);
int id = 0;
for (int i = 0; i < n; i++) {
sort(g[i].begin(), g[i].end());
int l = 0, r;
while (l < (int) g[i].size()) {
r = l;
while (r + 1 < (int) g[i].size() && g[i][r + 1] == g[i][r] + 1) r++;
sum[id] = r - l + 1;
segs[i].push_back({g[i][l], g[i][r], id++});
l = r + 1;
}
}
for (int i = 0; i < n; i++) g[i].clear();
for (int i = 1; i < n; i++) {
/// add the edges!
int ant_p = 0;
for (auto &seg : segs[i]) {
ant_p = 0;
while (true) {
if (ant_p == (int) segs[i - 1].size()) break;
if (segs[i - 1][ant_p].r < seg.l) ant_p++;
else break;
}
int first_good = ant_p;
while (true) {
if (ant_p == (int) segs[i - 1].size()) break;
if (segs[i - 1][ant_p].l > seg.r) break;
bool notisect = (segs[i - 1][ant_p].r < seg.l || seg.r < segs[i - 1][ant_p].l);
if (notisect) {
assert(0);
}
addEdge(segs[i - 1][ant_p].id, seg.id);
ant_p++;
}
ant_p = first_good;
}
}
n = id;
dfs1(0);
dfs2(sol, 0);
return sol;
}
int DistanceSum(int n, int *x, int *y) {
{
int __x = x[0], __y = y[0];
for (int i = 1; i < n; i++) {
__x = min(__x, x[i]);
__y = min(__y, y[i]);
}
for (int i = 0; i < n; i++) {
x[i] -= __x;
y[i] -= __y;
}
for (int i = 0; i < n; i++) {
assert(0 <= x[i] && x[i] < n);
assert(0 <= y[i] && y[i] < n);
}
}
return add(compute(n, x, y), compute(n, y, x));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
2 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
4 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
3 ms |
4940 KB |
Output is correct |
7 |
Correct |
3 ms |
4940 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
2 ms |
4940 KB |
Output is correct |
11 |
Correct |
2 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
5068 KB |
Output is correct |
6 |
Correct |
5 ms |
5068 KB |
Output is correct |
7 |
Correct |
4 ms |
5068 KB |
Output is correct |
8 |
Correct |
3 ms |
4940 KB |
Output is correct |
9 |
Correct |
3 ms |
4940 KB |
Output is correct |
10 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5324 KB |
Output is correct |
2 |
Correct |
8 ms |
5756 KB |
Output is correct |
3 |
Correct |
15 ms |
6164 KB |
Output is correct |
4 |
Correct |
14 ms |
6428 KB |
Output is correct |
5 |
Correct |
30 ms |
7424 KB |
Output is correct |
6 |
Correct |
37 ms |
7936 KB |
Output is correct |
7 |
Correct |
28 ms |
7944 KB |
Output is correct |
8 |
Correct |
28 ms |
7300 KB |
Output is correct |
9 |
Correct |
30 ms |
7796 KB |
Output is correct |
10 |
Correct |
39 ms |
11004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
5964 KB |
Output is correct |
2 |
Correct |
9 ms |
5872 KB |
Output is correct |
3 |
Correct |
21 ms |
7488 KB |
Output is correct |
4 |
Correct |
20 ms |
7112 KB |
Output is correct |
5 |
Correct |
50 ms |
9956 KB |
Output is correct |
6 |
Correct |
36 ms |
8456 KB |
Output is correct |
7 |
Correct |
46 ms |
9800 KB |
Output is correct |
8 |
Correct |
34 ms |
8640 KB |
Output is correct |
9 |
Correct |
32 ms |
7880 KB |
Output is correct |
10 |
Correct |
30 ms |
8068 KB |
Output is correct |