#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define eb emplace_back
using ii = pair<int, int>;
int rep[100005];
vector<ii> row[100005], col[100005];
namespace ufds {
int lnk[100005], sz[100005];
void init(int n) {
iota(lnk, lnk + n, 0);
fill(sz, sz + n, 1);
}
int find(int x) {
if (x == lnk[x]) return x;
return lnk[x] = find(lnk[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
lnk[b] = a;
}
};
int DistanceSum(int N, int X[], int Y[]) {
int ans = 0, min_X = *min_element(X, X + N), min_Y = *min_element(Y, Y + N);
for (int i = 0; i < N; i++) {
X[i] -= min_X;
Y[i] -= min_Y;
row[X[i]].eb(Y[i], i);
col[Y[i]].eb(X[i], i);
}
for (int i = 0; i < N; i++) {
sort(row[i].begin(), row[i].end());
sort(col[i].begin(), col[i].end());
}
for (auto dim : {row, col}) {
ufds::init(N);
int cnt = 0, ccs = 0, cur_prod = 0, tot_sz = 0;
for (int i = 0; i < N; i++) {
int prv_j = -1, prv_idx = -1;
for (auto [j, cur] : dim[i]) {
int upper = -1, idx;
if (i) {
auto it = lower_bound(dim[i - 1].begin(), dim[i - 1].end(), mp(j, 0));
if (it != dim[i - 1].end() && it->first == j) {
upper = ufds::find(rep[it->second]);
}
}
if (upper == -1) {
idx = cnt++;
ccs++;
cur_prod += tot_sz;
tot_sz++;
} else {
idx = upper;
cur_prod += tot_sz - ufds::sz[upper];
ufds::sz[upper]++;
tot_sz++;
}
rep[cur] = idx;
if (prv_j != -1 && prv_j + 1 == j) {
if (ufds::find(prv_idx) != ufds::find(idx)) {
ccs--;
cur_prod -= ufds::sz[ufds::find(prv_idx)] * (tot_sz - ufds::sz[ufds::find(prv_idx)]);
tot_sz -= ufds::sz[ufds::find(prv_idx)];
cur_prod -= ufds::sz[ufds::find(idx)] * (tot_sz - ufds::sz[ufds::find(idx)]);
tot_sz -= ufds::sz[ufds::find(idx)];
ufds::unite(prv_idx, idx);
cur_prod += tot_sz * ufds::sz[ufds::find(prv_idx)];
tot_sz += ufds::sz[ufds::find(prv_idx)];
}
}
prv_j = j;
prv_idx = idx;
}
//~ cout << "@ " << i << ' ' << cur_prod << ' ' << tot_sz << endl;
ans += 2 * cur_prod + tot_sz * (N - tot_sz);
}
}
for (auto dim : {row, col}) {
ufds::init(N);
int cnt = 0, ccs = 0, cur_prod = 0, tot_sz = 0;
for (int i = N - 1; i >= 0; i--) {
int prv_j = -1, prv_idx = -1;
for (auto [j, cur] : dim[i]) {
int upper = -1, idx;
if (i + 1 < N) {
auto it = lower_bound(dim[i + 1].begin(), dim[i + 1].end(), mp(j, 0));
if (it != dim[i + 1].end() && it->first == j) {
upper = ufds::find(rep[it->second]);
}
}
if (upper == -1) {
idx = cnt++;
ccs++;
cur_prod += tot_sz;
tot_sz++;
} else {
idx = upper;
cur_prod += tot_sz - ufds::sz[upper];
ufds::sz[upper]++;
tot_sz++;
}
rep[cur] = idx;
if (prv_j != -1 && prv_j + 1 == j) {
if (ufds::find(prv_idx) != ufds::find(idx)) {
ccs--;
cur_prod -= ufds::sz[ufds::find(prv_idx)] * (tot_sz - ufds::sz[ufds::find(prv_idx)]);
tot_sz -= ufds::sz[ufds::find(prv_idx)];
cur_prod -= ufds::sz[ufds::find(idx)] * (tot_sz - ufds::sz[ufds::find(idx)]);
tot_sz -= ufds::sz[ufds::find(idx)];
ufds::unite(prv_idx, idx);
cur_prod += tot_sz * ufds::sz[ufds::find(prv_idx)];
tot_sz += ufds::sz[ufds::find(prv_idx)];
}
}
prv_j = j;
prv_idx = idx;
}
//~ cout << "@ " << i << ' ' << cur_prod << ' ' << tot_sz << endl;
ans += 2 * cur_prod;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5020 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
6100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
6148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
