#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000000;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
ll mod(ll a, ll b) { return ((a%b) + b) % b; }
vector<int> compact(int N, int *arr) {
vector<int> ret(arr, arr+N);
int mi = *min_element(ret.begin(), ret.end()); mi--;
for(int i = 0; i < N; i++) ret[i] -= mi;
return ret;
}
plll dfs(int x, vector<int> &cnt, vector<vector<int>> &E, vector<bool> &chk) {
if(chk[x]) return {0LL, {0LL, 0LL}};
chk[x] = true;
plll ret = {0LL, {cnt[x], 0LL}};
for(auto i : E[x]) {
plll tmp = dfs(i, cnt, E, chk);
ret = {(ret.fi+tmp.fi+(ret.se.fi*(tmp.se.fi+tmp.se.se))%P+ret.se.se*tmp.se.fi)%P,
{(tmp.se.fi+ret.se.fi)%P, (tmp.se.se+ret.se.se+tmp.se.fi)%P}};
}
//cout << x << " " << ret << "\n";
return ret;
}
int solve(int N, vector<int> X, vector<int> Y) {
vector<vector<int>> P(101010);
vector<vector<piii>> V(P.size());
vector<int> cnt;
for(int i = 0; i < N; i++) P[X[i]].push_back(Y[i]);
for(int i = 0; i < P.size(); i++) {
if(P[i].empty()) continue;
sort(P[i].begin(), P[i].end());
V[i].push_back({P[i][0], {0, cnt.size()}});
for(int j = 1; j < P[i].size(); j++) {
++V[i].back().se.fi;
if(P[i][j] > P[i][j-1]+1) {
cnt.push_back(V[i].back().se.fi);
V[i].push_back({P[i][j], {0, cnt.size()}});
}
}
cnt.push_back(++V[i].back().se.fi);
}
//cout << cnt << " " << V;
vector<vector<int>> E(cnt.size());
for(int i = 1; i < P.size(); i++) {
for(int j = 0, k = 0; j < P[i].size(); j++) {
if(k+1 < V[i].size() && P[i][j] == V[i][k+1].fi) k++;
piii tmp = {P[i][j], {INF, INF}};
auto iter = upper_bound(V[i-1].begin(), V[i-1].end(), tmp);
if(iter == V[i-1].begin()) continue;
int x = V[i][k].se.se, y = (--iter)->se.se;
if(E[x].empty() || E[x].back() != y) {
E[x].push_back(y);
E[y].push_back(x);
}
}
}
//cout << " " << E;
vector<bool> chk(cnt.size(), false);
plll ret = dfs(0, cnt, E, chk);
//cout << ret.fi << "\n";
return ret.fi;
}
int DistanceSum(int N, int *X, int *Y) {
vector<int> A = compact(N, X), B = compact(N, Y);
int xx = solve(N, A, B), yy = solve(N, B, A);
return (xx+yy)%P;
}
Compilation message
city.cpp: In function 'int solve(int, std::vector<int>, std::vector<int>)':
city.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0; i < P.size(); i++) {
| ~~^~~~~~~~~~
city.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int j = 1; j < P[i].size(); j++) {
| ~~^~~~~~~~~~~~~
city.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i = 1; i < P.size(); i++) {
| ~~^~~~~~~~~~
city.cpp:60:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int j = 0, k = 0; j < P[i].size(); j++) {
| ~~^~~~~~~~~~~~~
city.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if(k+1 < V[i].size() && P[i][j] == V[i][k+1].fi) k++;
| ~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
5 ms |
4948 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
4948 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
5716 KB |
Output is correct |
| 2 |
Correct |
13 ms |
5844 KB |
Output is correct |
| 3 |
Correct |
18 ms |
6612 KB |
Output is correct |
| 4 |
Correct |
20 ms |
6704 KB |
Output is correct |
| 5 |
Correct |
32 ms |
8256 KB |
Output is correct |
| 6 |
Correct |
31 ms |
8516 KB |
Output is correct |
| 7 |
Correct |
36 ms |
8612 KB |
Output is correct |
| 8 |
Correct |
42 ms |
8224 KB |
Output is correct |
| 9 |
Correct |
42 ms |
8640 KB |
Output is correct |
| 10 |
Correct |
51 ms |
15688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
6860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
