#include <bits/stdc++.h>
using namespace std;
//find sum of distances
//ranges of blocks in columns/rows can be seen as nodes in a tree
//adjacent if they are connected in the real city, weight of node = number of cells in its range
//formula for sum = sum of distances between each pair of blocks = number of cells in range 1 * number in range 2 * distance horizontally
//end formula = S(e) * S'(e) with e as every edge in the graph and the two sums the sums over weights in the two compartments the tree is divided into
const int MAXN = 1e5+25;
const long long MOD = 1e9;
pair<int,int> pos[MAXN],range[MAXN];
int sum[MAXN];
vector<int> adj[MAXN];
map<pair<int,int>,int> node;
set<pair<int,int>> edges;
bool cmp(pair<int,int> x, pair<int,int> y){
return x.second<y.second;
}
void dfs(int u, int p){
for(auto v : adj[u]){
if(v != p){
dfs(v,u);
sum[u] += sum[v];
}
}
}
int finden(pair<int,int> p){
auto it = node.find(p);
if(it == node.end()){
return -1;
}
return it->second;
}
int DistanceSum(int N, int *X, int *Y){
long long ans = 0;
for(int i = 1;i<=N;++i){
pos[i].first = X[i-1];
pos[i].second = Y[i-1];
}
for(int id = 0;id<2;++id){
edges.clear(); node.clear();
for(int i = 1;i<=N;++i){
adj[i].clear();
node[make_pair(pos[i].first,pos[i].second)] = -2;
}
sort(pos+1,pos+N+1,cmp);
int cnt = 0;
for(int i = 1;i<=N;++i){
int it = finden(make_pair(pos[i].first,pos[i].second-1));
if(it == -1){
it = ++cnt;
range[cnt].first = pos[i].second;
}
node[make_pair(pos[i].first,pos[i].second)] = it;
if(finden(make_pair(pos[i].first,pos[i].second+1)) == -1){
range[cnt].second = pos[i].second;
sum[it] = range[it].second-range[it].first+1;
}
}
for(int i = 1;i<=N;++i){
int it = finden(make_pair(pos[i].first,pos[i].second));
int it2 = finden(make_pair(pos[i].first-1,pos[i].second));
if(it != -1 && it2 != -1){
edges.emplace(it,it2);
edges.emplace(it2,it);
}
}
for(auto p : edges) adj[p.first].push_back(p.second);
dfs(1,-1);
for(int i = 1;i<=cnt;++i) ans += 1LL*sum[i]*(sum[1]-sum[i]);
for(int i = 1;i<=N;++i) swap(pos[i].first,pos[i].second);
}
ans %= MOD;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2804 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
4472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
5440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
