#include <algorithm>
#include <vector>
using namespace std;
typedef long long llong;
typedef pair<int, int> pi;
int n;
const int MOD = 1e9;
const int PMAX = 2147483646;
pi point[100000];
int idx[100000];
int cnt[100000];
vector<int> edge[100000];
bool haveNext(int i) {
if (i == n - 1) return false;
if (point[i].first != point[i + 1].first) return false;
if (point[i].second + 1 != point[i + 1].second) return false;
return true;
}
int bsearch(pi x) {
int s = 0, e = n - 1;
int m;
while (s < e) {
m = (s + e) / 2;
if (point[m] == x) return m;
if (point[m] < x) s = m + 1;
else e = m - 1;
}
if (point[s] == x) return s;
return -1;
}
int ans;
int dfs(int x, int p) {
int ret = cnt[x];
for (int i : edge[x]) {
if (i == p) continue;
ret += dfs(i, x);
}
if (x) {
llong sum = ret;
sum *= n - ret;
ans = (ans + sum) % MOD;
}
return ret;
}
int getAns() {
ans = 0;
sort(point, point + n);
idx[0] = 0;
edge[0].clear();
cnt[0] = 1;
for (int i = 1; i < n; ++i) {
if (haveNext(i - 1)) ++cnt[idx[i] = idx[i - 1]];
else cnt[idx[i] = idx[i - 1] + 1] = 1, edge[idx[i]].clear();
int j = bsearch({ point[i].first - 1, point[i].second });
if (j == -1) continue;
if (!edge[idx[i]].empty() && idx[j] == edge[idx[i]].back()) continue;
edge[idx[i]].push_back(idx[j]);
edge[idx[j]].push_back(idx[i]);
}
dfs(0, -1);
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for (int i = 0; i < n; ++i) {
point[i] = { X[i], Y[i] };
}
int t = getAns();
for (int i = 0; i < n; ++i) {
point[i] = { Y[i], X[i] };
}
return (getAns() + t) % MOD;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
5212 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
5212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5356 KB |
Output is correct |
| 2 |
Correct |
13 ms |
5356 KB |
Output is correct |
| 3 |
Correct |
39 ms |
5604 KB |
Output is correct |
| 4 |
Correct |
26 ms |
5604 KB |
Output is correct |
| 5 |
Correct |
63 ms |
5996 KB |
Output is correct |
| 6 |
Correct |
59 ms |
5996 KB |
Output is correct |
| 7 |
Correct |
59 ms |
5996 KB |
Output is correct |
| 8 |
Correct |
59 ms |
5996 KB |
Output is correct |
| 9 |
Correct |
63 ms |
6152 KB |
Output is correct |
| 10 |
Correct |
63 ms |
8268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
5620 KB |
Output is correct |
| 2 |
Correct |
13 ms |
5488 KB |
Output is correct |
| 3 |
Correct |
33 ms |
6264 KB |
Output is correct |
| 4 |
Correct |
33 ms |
6000 KB |
Output is correct |
| 5 |
Correct |
73 ms |
7316 KB |
Output is correct |
| 6 |
Correct |
66 ms |
6576 KB |
Output is correct |
| 7 |
Correct |
73 ms |
7352 KB |
Output is correct |
| 8 |
Correct |
56 ms |
6524 KB |
Output is correct |
| 9 |
Correct |
66 ms |
6392 KB |
Output is correct |
| 10 |
Correct |
63 ms |
6392 KB |
Output is correct |
