#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pii pair<int,int>
#define mod 1000000000
#define SIZE 100005
using namespace std;
int n;
vector<pii> cell , cell2;
long long int arr[SIZE] , sz[SIZE] , dp[SIZE] , pr[SIZE];
vector<int> graph[SIZE];
long long int ans;
long long int SUM;
bool cmp(pii A , pii B) {
if (A.second == B.second) return A.first < B.first;
return A.second < B.second;
}
void init() {
memset(arr , 0 , sizeof(arr));
memset(dp , 0 , sizeof(dp));
memset(sz , 0 , sizeof(sz));
for (int i = 0; i < SIZE; i++) graph[i].clear();
SUM = 0;
}
void make_tree(int here) {
for (auto there : graph[here]) {
if (pr[there] == -1) {
pr[there] = here;
make_tree(there);
}
}
}
void solve(int here) {
long long int res = 0;
sz[here] = arr[here];
for (auto there : graph[here]) {
if (there == pr[here]) continue;
solve(there);
sz[here] += sz[there];
}
ans += sz[here]*(SUM-sz[here]);
ans %= mod;
}
void make_graph() {
sort(cell.begin() , cell.end() , cmp);
// cout << "=======\n";
for (auto t : cell) {
//cout << t.first << " " << t.second << "\n";
}
long long int s = cell[0].first;
long long int e = cell[0].first;
int siz = 0;
vector<pair<int, pii> > tmp;
vector<int> yidx;
for (int i = 0; i < cell.size()-1; i++) {
if (cell[i].second == cell[i+1].second && cell[i+1].first-cell[i].first == 1) e++;
else {
tmp.push_back({cell[i].second , {s , e}});
arr[siz++] = e-s+1;
yidx.push_back(cell[i].second);
s = cell[i+1].first;
e = cell[i+1].first;
}
}
tmp.push_back({cell[cell.size()-1].second , {s , e}});
arr[siz++] = e-s+1;
yidx.push_back(cell[cell.size()-1].second);
for (int i = 0; i < siz; i++) SUM += arr[i];
//printf("ok1\n");
sort(tmp.begin() , tmp.end());
sort(yidx.begin() , yidx.end());
yidx.push_back(1e18);
for (int i = 0; i < tmp.size(); i++) {
auto t = tmp[i];
// cout << t.first << " " << t.second.first << " " << t.second.second << " : ";
// cout << arr[i] << "\n";
}
for (int idx = 0; idx < tmp.size(); idx++) {
int y = tmp[idx].first;
int s = tmp[idx].second.first;
int e = tmp[idx].second.second;
int idx1 = lower_bound(yidx.begin() , yidx.end() , y+1)-yidx.begin();
int idx2 = upper_bound(yidx.begin() , yidx.end() , y+1)-yidx.begin();
idx2--;
if (idx1 == yidx.size()-1) continue;
int l = idx1;
int r = idx2;
// printf("ok1\n");
while(l < r) {
int mid = (l+r)/2;
if (tmp[mid].second.second >= s) r = mid;
else l = mid+1;
}
//printf("ok2\n");
int lo = l;
l = idx1;
r = idx2;
while(l < r) {
int mid = (l+r+1)/2;
//printf("%d %d %d\n" , l , r , mid);
if (tmp[mid].second.first <= e) l = mid;
else r = mid-1;
}
// printf("ok3\n");
int hi = l;
for (int i = lo; i <= hi; i++) {
graph[idx].push_back(i);
graph[i].push_back(idx);
//cout << idx << " " << i << "\n";
}
}
memset(pr , -1 , sizeof(pr));
pr[0] = 0;
make_tree(0);
}
int DistanceSum(int N , int *X , int *Y) {
n = N;
for (int i = 0; i < n; i++) {
cell.push_back({X[i] , Y[i]});
cell2.push_back({Y[i] , X[i]});
}
make_graph();
solve(0);
ans %= mod;
init();
for (int i = 0; i < cell.size(); i++) cell[i] = cell2[i];
make_graph();
solve(0);
ans %= mod;
return ans;
}
Compilation message
city.cpp: In function 'void solve(int)':
city.cpp:39:19: warning: unused variable 'res' [-Wunused-variable]
39 | long long int res = 0;
| ^~~
city.cpp: In function 'void make_graph()':
city.cpp:57:15: warning: variable 't' set but not used [-Wunused-but-set-variable]
57 | for (auto t : cell) {
| ^
city.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < cell.size()-1; i++) {
| ~~^~~~~~~~~~~~~~~
city.cpp:86:20: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
86 | yidx.push_back(1e18);
| ^~~~
city.cpp:88:23: 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]
88 | for (int i = 0; i < tmp.size(); i++) {
| ~~^~~~~~~~~~~~
city.cpp:89:14: warning: variable 't' set but not used [-Wunused-but-set-variable]
89 | auto t = tmp[i];
| ^
city.cpp:94:27: 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]
94 | for (int idx = 0; idx < tmp.size(); idx++) {
| ~~~~^~~~~~~~~~~~
city.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if (idx1 == yidx.size()-1) continue;
| ~~~~~^~~~~~~~~~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:152:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int i = 0; i < cell.size(); i++) cell[i] = cell2[i];
| ~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
5716 KB |
Output is correct |
| 2 |
Runtime error |
123 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
124 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
11 ms |
6528 KB |
Output is correct |
| 2 |
Correct |
12 ms |
6544 KB |
Output is correct |
| 3 |
Correct |
23 ms |
7528 KB |
Output is correct |
| 4 |
Correct |
22 ms |
7596 KB |
Output is correct |
| 5 |
Correct |
50 ms |
9144 KB |
Output is correct |
| 6 |
Correct |
46 ms |
9080 KB |
Output is correct |
| 7 |
Correct |
45 ms |
9396 KB |
Output is correct |
| 8 |
Correct |
45 ms |
9016 KB |
Output is correct |
| 9 |
Correct |
44 ms |
9252 KB |
Output is correct |
| 10 |
Correct |
50 ms |
12344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
132 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
