This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#include "city.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(), x.end()
const int N = 2e5+5, inf = INT_MAX;
const vector<pair<int, int>> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int n, X[N], Y[N], cntX[2][N], cntY[2][N];
ll ans, dp[N];
vector<pair<int, int>> cellX[N], cellY[N];
bitset<N> vis;
bool ok(int x, int y) {
return min(x, y) >= 0;
}
void bfs(int idx) {
queue<pair<int, int>> q;
q.push(make_pair(0, idx));
while (!q.empty()) {
int d = q.front().first;
int nwIdx = q.front().second;
q.pop();
if (vis[nwIdx]) continue;
vis[nwIdx] = 1;
dp[idx] += d;
int x = X[nwIdx];
int y = Y[nwIdx];
for (auto [a, b] : dir) {
if (!ok(x+a, y+b)) continue;
auto it = lower_bound(all(cellX[x+a]), make_pair(y+b, 0));
if (it != cellX[x+a].end() && it->first == y+b && !vis[it->second]) {
q.push(make_pair(d+1, it->second));
}
}
}
}
void dfs(int idx) {
vis[idx] = 1;
int x = X[idx];
int y = Y[idx];
// arriba
if (ok(x-1, y)) {
auto it = lower_bound(all(cellX[x-1]), make_pair(y, 0));
if (it != cellX[x-1].end() && it->first == y && !vis[it->second]) {
dp[it->second] = dp[idx] + n - (x ? cntX[0][x-1]*2 : 0); // elementos con x' <= x-1
dfs(it->second);
}
}
// abajo
if (ok(x+1, y)) {
auto it = lower_bound(all(cellX[x+1]), make_pair(y, 0));
if (it != cellX[x+1].end() && it->first == y && !vis[it->second]) {
dp[it->second] = dp[idx] + n - cntX[1][x+1]*2; // elementos con x' >= x+1
dfs(it->second);
}
}
// derecha
if (ok(x, y+1)) {
auto it = lower_bound(all(cellX[x]), make_pair(y+1, 0));
if (it != cellX[x].end() && it->first == y+1 && !vis[it->second]) {
dp[it->second] = dp[idx] + n - cntY[1][y+1]*2; // elementos con y' >= y+1
dfs(it->second);
}
}
// izquierda
if (ok(x, y-1)) {
auto it = lower_bound(all(cellX[x]), make_pair(y-1, 0));
if (it != cellX[x].end() && it->first == y-1 && !vis[it->second]) {
dp[it->second] = dp[idx] + n - (y ? cntY[0][y-1]*2 : 0); // elementos con y' >= y+1
dfs(it->second);
}
}
}
int DistanceSum(int NN, int *XX, int *YY) {
n = NN;
ans = 0;
int mnX = inf;
int mnY = inf;
for (int i = 0; i < n; i++) {
X[i] = XX[i];
Y[i] = YY[i];
mnX = min(mnX, X[i]);
mnY = min(mnY, Y[i]);
}
for (int i = 0; i < n; i++) {
X[i] -= mnX;
Y[i] -= mnY;
cellX[X[i]].push_back(make_pair(Y[i], i));
cellY[Y[i]].push_back(make_pair(X[i], i));
}
for (int i = 0; i < N; i++) {
sort(all(cellX[i]));
sort(all(cellY[i]));
}
for (int i = 0; i < N; i++) {
cntX[0][i] = (i ? cntX[0][i-1] : 0) + cellX[i].size();
cntY[0][i] = (i ? cntY[0][i-1] : 0) + cellY[i].size();
}
for (int i = N-1; i >= 0; i--) {
cntX[1][i] = (i+1 < N ? cntX[1][i+1] : 0) + cellX[i].size();
cntY[1][i] = (i+1 < N ? cntY[1][i+1] : 0) + cellY[i].size();
}
bfs(0);
vis.reset();
dfs(0);
for (int i = 0; i < n; i++) {
ans += dp[i];cerr << dp[i] << endl;
}
return ans/2;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |