#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#define pii pair<int,int>
#define F first
#define S second
#define ll long long int
using namespace std;
const int MOD = 1e9, maxN = 1e5 + 326;
const long long int INF = (1LL << 31) - 2;
int mp[2020][2020], vis[maxN], d[maxN], dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
queue<int> que;
vector<pii> pos;
inline ll add(ll a, ll b){
return (a + b >= MOD ? a + b - MOD : a + b);
}
inline ll sub(ll a, ll b){
return (a >= b ? a - b : a - b + MOD);
}
struct BIT{
ll arr[maxN];
BIT(){}
void modify(int p, ll x){
for(; p < maxN; p += (p & -p)) arr[p] = add(arr[p], x);
}
int sum(int p){
int r = 0;
for(; p; p -= (p & -p)) r = add(r, arr[p]);
return r;
}
} cnt, xy, xy2;
int DistanceSum(int N, int *X, int *Y) {
if(N <= 5000){
int minX = INF, minY = INF;
for(int i = 0; i < N; i++){
minX = min(minX, X[i]);
minY = min(minY, Y[i]);
}
for(int i = 0; i < N; i++){
X[i] -= minX - 1;
Y[i] -= minY - 1;
mp[X[i]][Y[i]] = i + 1;
}
long long int ans = 0;
for(int i = 0; i < N; i++){
fill(d, d + N, INF);
fill(vis, vis + N, false);
d[i] = 0;
que.push(i);
vis[i] = true;
//cout << "i = " << i << endl;
while(que.size()){
int id = que.front(); que.pop();
for(int j = 0; j < 4; j++){
if(mp[X[id] + dir[j][0]][Y[id] + dir[j][1]]){
int nid = mp[X[id] + dir[j][0]][Y[id] + dir[j][1]] - 1;
if(!vis[nid]){
d[nid] = d[id] + 1;
//cout << "d[" << i << "][" << nid << "] = " << d[nid] << endl;
ans = add(ans, d[nid]);
vis[nid] = true;
que.push(nid);
}
}
}
}
}
return ans / 2;
}
ll minX = INF, minY = INF;
for(int i = 0; i < N; i++){
minX = min(minX, (int)X[i]);
minY = min(minY, (int)Y[i]);
}
for(int i = 0; i < N; i++){
X[i] -= minX - 1;
Y[i] -= minY - 1;
pos.emplace_back(X[i], Y[i]);
}
sort(pos.begin(), pos.end());
long long int ans = 0;
//xy: x + y
//xy2: y - x
for(auto f : pos){
int x = f.F, y = f.S;
ans = add(ans, (MOD - xy.sum(y))% MOD);
ans = add(ans, cnt.sum(y) * add(x, y) % MOD);
ans = add(ans, sub(xy2.sum(maxN - 1), xy2.sum(y)) % MOD);
ans = add(ans, sub(cnt.sum(maxN - 1), cnt.sum(y)) * sub(x, y) % MOD);
cnt.modify(y, 1);
xy.modify(y, add(x, y));
xy2.modify(y, sub(y, x));
}
return (int)add(0, ans);
}
/*
int DistanceSum(int N, int *X, int *Y) {
if(N > maxN) return 0;
int minX = INF, minY = INF;
for(int i = 0; i < N; i++){
minX = min(minX, X[i]);
minY = min(minY, Y[i]);
}
for(int i = 0; i < N; i++){
X[i] -= minX - 1;
Y[i] -= minY - 1;
mp[X[i]][Y[i]] = i + 1;
}
long long int ans = 0;
for(int i = 0; i < N; i++){
fill(d, d + N, INF);
fill(vis, vis + N, false);
d[i] = 0;
que.push(i);
vis[i] = true;
//cout << "i = " << i << endl;
while(que.size()){
int id = que.front(); que.pop();
for(int j = 0; j < 4; j++){
if(mp[X[id] + dir[j][0]][Y[id] + dir[j][1]]){
int nid = mp[X[id] + dir[j][0]][Y[id] + dir[j][1]] - 1;
if(!vis[nid]){
d[nid] = d[id] + 1;
//cout << "d[" << i << "][" << nid << "] = " << d[nid] << endl;
ans = add(ans, d[nid]);
vis[nid] = true;
que.push(nid);
}
}
}
}
}
return ans / 2;
return 5;
int minX = INF, minY = INF;
for(int i = 0; i < N; i++){
minX = min(minX, X[i]);
minY = min(minY, Y[i]);
}
for(int i = 0; i < N; i++){
X[i] -= minX - 1;
Y[i] -= minY - 1;
pos.emplace_back(X[i], Y[i]);
}
sort(pos.begin(), pos.end());
long long int ans = 0;
for(auto f : pos){
int x = f.F, y = f.S;
ans = add(ans, MOD - xy.sum(y));
ans = add(ans, cnt.sum(y) * add(x, y) % MOD);
cnt.modify(y, 1);
xy.modify(y, add(x, y));
}
return add(0, ans);
}
*/
/*
int DistanceSum(int N, int *X, int *Y) {
if(N > maxN) return 0;
int minX = INF, minY = INF;
for(int i = 0; i < N; i++){
minX = min(minX, X[i]);
minY = min(minY, Y[i]);
}
for(int i = 0; i < N; i++){
X[i] -= minX - 1;
Y[i] -= minY - 1;
mp[X[i]][Y[i]] = i + 1;
}
long long int ans = 0;
for(int i = 0; i < N; i++){
fill(d, d + N, INF);
fill(vis, vis + N, false);
d[i] = 0;
que.push(i);
vis[i] = true;
//cout << "i = " << i << endl;
while(que.size()){
int id = que.front(); que.pop();
for(int j = 0; j < 4; j++){
if(mp[X[id] + dir[j][0]][Y[id] + dir[j][1]]){
int nid = mp[X[id] + dir[j][0]][Y[id] + dir[j][1]] - 1;
if(!vis[nid]){
d[nid] = d[id] + 1;
//cout << "d[" << i << "][" << nid << "] = " << d[nid] << endl;
ans = add(ans, d[nid]);
vis[nid] = true;
que.push(nid);
}
}
}
}
}
return ans / 2;
}
*/
Compilation message
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:80:29: error: no matching function for call to 'min(long long int&, int)'
80 | minX = min(minX, (int)X[i]);
| ^
In file included from /usr/include/c++/9/vector:60,
from city.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
198 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: template argument deduction/substitution failed:
city.cpp:80:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
80 | minX = min(minX, (int)X[i]);
| ^
In file included from /usr/include/c++/9/vector:60,
from city.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
246 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: template argument deduction/substitution failed:
city.cpp:80:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
80 | minX = min(minX, (int)X[i]);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from city.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3444 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: template argument deduction/substitution failed:
city.cpp:80:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
80 | minX = min(minX, (int)X[i]);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from city.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3450 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
city.cpp:80:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
80 | minX = min(minX, (int)X[i]);
| ^
city.cpp:81:29: error: no matching function for call to 'min(long long int&, int)'
81 | minY = min(minY, (int)Y[i]);
| ^
In file included from /usr/include/c++/9/vector:60,
from city.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
198 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: template argument deduction/substitution failed:
city.cpp:81:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
81 | minY = min(minY, (int)Y[i]);
| ^
In file included from /usr/include/c++/9/vector:60,
from city.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
246 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: template argument deduction/substitution failed:
city.cpp:81:29: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
81 | minY = min(minY, (int)Y[i]);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from city.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3444 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: template argument deduction/substitution failed:
city.cpp:81:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
81 | minY = min(minY, (int)Y[i]);
| ^
In file included from /usr/include/c++/9/algorithm:62,
from city.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3450 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: template argument deduction/substitution failed:
city.cpp:81:29: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
81 | minY = min(minY, (int)Y[i]);
| ^
