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;
typedef long long ll;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MAXN = 1e5 + 10;
const ll MOD = 1000000000;
int n, f[MAXN], sz;
vector<pll> vec;
ll ans = 0, dp[MAXN];
vector<int> adj[MAXN];
inline int get(ll x, ll y) {
pll e = pll(x, y);
auto it = lower_bound(all(vec), e);
if (it != vec.end() && *it == e) return it - vec.begin() + 1;
return 0;
}
void dfs(int v, int p) {
for (int u : adj[v]) {
if (u == p) continue;
dfs(u, v);
ans = (ans + 1ll * dp[u] * (n - dp[u])) % MOD;
dp[v] += dp[u];
}
}
inline void solve() {
sz = 0;
sort(all(vec));
memset(f, 0, sizeof f);
memset(dp, 0, sizeof dp);
for (int i = 0; i < MAXN; i++)
adj[i].clear();
for (int i = 0; i < n; i++) {
auto [x, y] = vec[i];
if (get(x, y - 1)) f[i + 1] = f[get(x, y - 1)];
else f[i + 1] = ++sz;
dp[f[i + 1]]++;
if (get(x - 1, y) && !(get(x, y - 1) && get(x - 1, y - 1)))
adj[f[get(x - 1, y)]].push_back(f[i + 1]), adj[f[i + 1]].push_back(f[get(x - 1, y)]);
}
dfs(1, 0);
}
int DistanceSum(int N, int *X, int *Y) {
n = N;
for (int i = 0; i < n; i++)
vec.push_back({X[i], Y[i]});
sort(all(vec));
solve();
for (auto e : vec)
swap(e.X, e.Y);
solve();
return ans % MOD;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |