#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;
}
pll dfs(int n, int x, vector<int> &cnt, vector<vector<int>> &E, vector<bool> &chk) {
if(chk[x]) return {0LL, 0LL};
chk[x] = true;
pll ret = {0LL, cnt[x]};
for(auto i : E[x]) {
pll tmp = dfs(n, i, cnt, E, chk);
ret = {(ret.fi+tmp.fi+tmp.se*(n-tmp.se))%P, (tmp.se+ret.se)%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(iter->fi+iter->se.fi <= P[i][j]) continue;
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);
pll ret = dfs(N, 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:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < P.size(); i++) {
| ~~^~~~~~~~~~
city.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int j = 1; j < P[i].size(); j++) {
| ~~^~~~~~~~~~~~~
city.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for(int i = 1; i < P.size(); i++) {
| ~~^~~~~~~~~~
city.cpp:59:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int j = 0, k = 0; j < P[i].size(); j++) {
| ~~^~~~~~~~~~~~~
city.cpp:60: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]
60 | if(k+1 < V[i].size() && P[i][j] == V[i][k+1].fi) k++;
| ~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
5 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4948 KB |
Output is correct |
| 5 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 6 |
Correct |
5 ms |
4988 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5048 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 11 |
Correct |
5 ms |
5076 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5044 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5052 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5204 KB |
Output is correct |
| 6 |
Correct |
7 ms |
5100 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5076 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5052 KB |
Output is correct |
| 10 |
Correct |
6 ms |
5084 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
5740 KB |
Output is correct |
| 2 |
Correct |
10 ms |
5752 KB |
Output is correct |
| 3 |
Correct |
20 ms |
6624 KB |
Output is correct |
| 4 |
Correct |
20 ms |
6648 KB |
Output is correct |
| 5 |
Correct |
32 ms |
8272 KB |
Output is correct |
| 6 |
Correct |
30 ms |
8352 KB |
Output is correct |
| 7 |
Correct |
32 ms |
8364 KB |
Output is correct |
| 8 |
Correct |
34 ms |
8260 KB |
Output is correct |
| 9 |
Correct |
32 ms |
8460 KB |
Output is correct |
| 10 |
Correct |
46 ms |
14212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
6356 KB |
Output is correct |
| 2 |
Correct |
13 ms |
6404 KB |
Output is correct |
| 3 |
Correct |
29 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
24 ms |
8040 KB |
Output is correct |
| 5 |
Correct |
53 ms |
12008 KB |
Output is correct |
| 6 |
Correct |
41 ms |
10248 KB |
Output is correct |
| 7 |
Correct |
50 ms |
12276 KB |
Output is correct |
| 8 |
Correct |
42 ms |
10316 KB |
Output is correct |
| 9 |
Correct |
39 ms |
9836 KB |
Output is correct |
| 10 |
Correct |
38 ms |
9720 KB |
Output is correct |
