// ~ Be Name Khoda ~ //
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 1e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 2e3 + 10;
const int mod = 2e9;
const ll inf = 1e18;
ll ans = 0;
vector <int> avx, av[maxn5];
map <int, int> inner[maxn5];
int ptx[maxn5], par[maxn5];
inline void fix(ll &a){
if(a >= mod)
a -= mod;
if(a < 0)
a += mod;
}
struct __node{
vector <int> adj;
int n, inin;
ll dissum, dissumup, nup;
inline void clear(){
n = inin = 0;
dissum = dissumup = nup = 0;
adj.clear();
}
inline void rebuild_adj(){
sort(all(adj));
adj.resize(unique(all(adj)) - adj.begin());
adj.shrink_to_fit();
}
inline void sumup(int ty){
//cout << "here " << ty << ' ' << dissum << ' ' << n << ' ' << dissumup << ' ' << nup << endl;
if(ty != -1){
fix(dissum += dissumup);
n += nup;
}
fix(ans += dissum * inin % mod);
//cout << "then " << dissum << ' ' << n << ' ' << inin << ' ' << ans << endl;
}
} node[maxn5], up[maxn5], tmp;
void dfs_up(int v){
//cout << "aha " << v << ' ' << par[v] << ' ' << node[v].n << endl;
for(auto u : node[v].adj) if(u != par[v]){
par[u] = v;
dfs_up(u);
fix(node[v].dissum += node[u].dissum);
fix(node[v].dissum += node[u].n);
node[v].n += node[u].n;
}
}
void dfs_dw(int v){
//cout << "summing up " << v << endl;
node[v].sumup(par[v]);
for(auto u : node[v].adj) if(u != par[v]){
fix(node[u].dissumup = node[v].dissum + node[v].n);
fix(node[u].dissumup -= node[u].dissum);
fix(node[u].dissumup -= node[u].n);
fix(node[u].dissumup -= node[u].n);
node[u].nup = node[v].n - node[u].n;
dfs_dw(u);
}
}
inline int solve(int n, int *x, int *y){
ans = 0;
avx.clear();
for(int i = 0; i < n; i++)
avx.pb(x[i]);
sort(all(avx));
avx.resize(unique(all(avx)) - avx.begin());
for(int i = 0; i < avx.size(); i++){
av[i].clear();
inner[i].clear();
}
for(int i = 0; i < n; i++){
ptx[i] = lower_bound(all(avx), x[i]) - avx.begin();
av[ptx[i]].pb(y[i]);
}
int newid = 0;
for(int i = 0; i < avx.size(); i++){
sort(all(av[i]));
int last = 0;
for(int j = 1; j < av[i].size(); j++){
if(av[i][j] != av[i][j - 1] + 1){
node[newid].clear();
node[newid].n = node[newid].inin = j - last;
for(int k = last; k < j; k++)
inner[i][av[i][k]] = newid;
newid++;
last = j;
}
}
node[newid].clear();
node[newid].n = node[newid].inin = int(av[i].size()) - last;
for(int k = last; k < av[i].size(); k++)
inner[i][av[i][k]] = newid;
newid++;
}
for(int i = 0; i < n; i++){
int k = inner[ptx[i]][y[i]];
if(ptx[i] && inner[ptx[i] - 1].find(y[i]) != inner[ptx[i] - 1].end())
node[k].adj.pb(inner[ptx[i] - 1][y[i]]);
if(ptx[i] + 1 < avx.size() && inner[ptx[i] + 1].find(y[i]) != inner[ptx[i] + 1].end())
node[k].adj.pb(inner[ptx[i] + 1][y[i]]);
}
for(int i = 0; i < newid; i++)
node[i].rebuild_adj();
par[0] = -1;
dfs_up(0);
dfs_dw(0);
return ans;
}
int DistanceSum(int n, int *x, int *y){
int ans = solve(n, x, y);
//cout << "here " << ans << endl;
ans = (ans + solve(n, y, x));
//cout << "now " << ans << endl;
return (ans % mod) / 2;
}
Compilation message
city.cpp: In function 'int solve(int, int*, int*)':
city.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int i = 0; i < avx.size(); i++){
| ~~^~~~~~~~~~~~
city.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i = 0; i < avx.size(); i++){
| ~~^~~~~~~~~~~~
city.cpp:110:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int j = 1; j < av[i].size(); j++){
| ~~^~~~~~~~~~~~~~
city.cpp:122:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int k = last; k < av[i].size(); k++)
| ~~^~~~~~~~~~~~~~
city.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | if(ptx[i] + 1 < avx.size() && inner[ptx[i] + 1].find(y[i]) != inner[ptx[i] + 1].end())
| ~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
18216 KB |
Output is correct |
| 2 |
Correct |
9 ms |
18320 KB |
Output is correct |
| 3 |
Correct |
10 ms |
18276 KB |
Output is correct |
| 4 |
Correct |
8 ms |
18260 KB |
Output is correct |
| 5 |
Correct |
8 ms |
18260 KB |
Output is correct |
| 6 |
Correct |
9 ms |
18260 KB |
Output is correct |
| 7 |
Correct |
8 ms |
18260 KB |
Output is correct |
| 8 |
Correct |
8 ms |
18344 KB |
Output is correct |
| 9 |
Correct |
8 ms |
18244 KB |
Output is correct |
| 10 |
Correct |
8 ms |
18276 KB |
Output is correct |
| 11 |
Correct |
8 ms |
18260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
18388 KB |
Output is correct |
| 2 |
Correct |
8 ms |
18388 KB |
Output is correct |
| 3 |
Correct |
9 ms |
18388 KB |
Output is correct |
| 4 |
Correct |
9 ms |
18464 KB |
Output is correct |
| 5 |
Correct |
9 ms |
18516 KB |
Output is correct |
| 6 |
Correct |
9 ms |
18432 KB |
Output is correct |
| 7 |
Correct |
12 ms |
18468 KB |
Output is correct |
| 8 |
Correct |
10 ms |
18496 KB |
Output is correct |
| 9 |
Correct |
12 ms |
18388 KB |
Output is correct |
| 10 |
Correct |
9 ms |
18388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
20052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
20192 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
20420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
