#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define mp make_pair
#define pub push_back
#define pob pop_back()
#define ss second
#define ff first
#define mt make_tuple
#define pof pop_front()
#define fbo find_by_order
#define ook order_of_key
#define lb lower_bound
#define ub upper_bound
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
ll ans, mod = 1e9, sum, z, tr[100001], w[100001], h[4] = {0, 0, 1, -1}, v[4] = {1, -1, 0, 0}, sub[100001];
pii p[100001];
vector <int> edg[100001];
map<int, int> m[100001], hs[100001], idx[100001];
void dfs(int u, int par)
{
sub[u] = w[u];
for (auto x : edg[u])
if ( x != par )
dfs(x, u);
sub[par] += sub[u];
}
void dfs1(int u, int par)
{
ans = (ans + ((sum - sub[u]) * sub[u]) % mod) % mod;
for (auto x : edg[u])
if ( x != par )
dfs1(x, u);
}
void solve(int n, int *x, int *y) {
sum = n;
z = 0;
memset(w, 0, sizeof w);
for (int i = 0; i < n; i++)
{
p[i].ff = x[i];
p[i].ss = y[i];
edg[i].clear();
m[i].clear();
hs[i].clear();
idx[i].clear();
}
sort(p, p + n);
for (int i = 0; i < n; i++)
{
if ( !i || p[i].ff != p[i - 1].ff || p[i].ss > p[i - 1].ss + 1 )
{
tr[i] = ++z;
m[p[i].ff][p[i].ss] = z;
w[z]++;
} else {
tr[i] = tr[i - 1];
m[p[i].ff][p[i].ss] = tr[i - 1];
w[tr[i - 1]]++;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 4; j++)
{
if ( p[i].ff + h[j] >= 0 && p[i].ff + h[j] <= n && p[i].ss + v[j] >= 0 && p[i].ss + v[j] <= n && m[p[i].ff + h[j]][p[i].ss + v[j]] && !hs[tr[i]][m[p[i].ff + h[j]][p[i].ss + v[j]]] && tr[i] != m[p[i].ff + h[j]][p[i].ss + v[j]] )
{
hs[tr[i]][m[p[i].ff + h[j]][p[i].ss + v[j]]] = hs[m[p[i].ff + h[j]][p[i].ss + v[j]]][tr[i]] = 1;
edg[tr[i]].pub(m[p[i].ff + h[j]][p[i].ss + v[j]]);
edg[m[p[i].ff + h[j]][p[i].ss + v[j]]].pub(tr[i]);
}
}
}
dfs(1, 0);
dfs1(1, 0);
}
int DistanceSum(int n, int *x, int *y) {
int mnx = INT_MAX, mny = INT_MAX;
for (int i = 0; i < n; i++)
{
mnx = min(mnx, x[i]);
mny = min(mny, y[i]);
}
for (int i = 0; i < n; i++)
{
x[i] -= mnx;
y[i] -= mny;
}
solve(n, x, y);
solve(n, y, x);
return ans;
}
//int main() {
// int tmp;
//
// int N, i;
// scanf("%d", &N);
//
// int sq_x[100001], sq_y[100001];
// for (i = 0; i < N; i++) {
// tmp = scanf("%d %d", &sq_x[i], &sq_y[i]);
// }
//
// int ds = DistanceSum(N, sq_x, sq_y);
// printf("%d\n", ds);
//
// return 0;
//
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
17536 KB |
Output is correct |
2 |
Correct |
17 ms |
17536 KB |
Output is correct |
3 |
Correct |
18 ms |
17528 KB |
Output is correct |
4 |
Correct |
18 ms |
17664 KB |
Output is correct |
5 |
Correct |
17 ms |
17536 KB |
Output is correct |
6 |
Correct |
16 ms |
17664 KB |
Output is correct |
7 |
Correct |
17 ms |
17664 KB |
Output is correct |
8 |
Correct |
16 ms |
17536 KB |
Output is correct |
9 |
Correct |
17 ms |
17656 KB |
Output is correct |
10 |
Correct |
16 ms |
17536 KB |
Output is correct |
11 |
Correct |
17 ms |
17536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
17792 KB |
Output is correct |
2 |
Correct |
18 ms |
17792 KB |
Output is correct |
3 |
Correct |
19 ms |
17792 KB |
Output is correct |
4 |
Correct |
19 ms |
17792 KB |
Output is correct |
5 |
Correct |
20 ms |
17920 KB |
Output is correct |
6 |
Correct |
20 ms |
17792 KB |
Output is correct |
7 |
Correct |
21 ms |
17920 KB |
Output is correct |
8 |
Correct |
22 ms |
17792 KB |
Output is correct |
9 |
Correct |
21 ms |
17792 KB |
Output is correct |
10 |
Correct |
21 ms |
17792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
44 ms |
19192 KB |
Output is correct |
2 |
Correct |
44 ms |
19380 KB |
Output is correct |
3 |
Correct |
90 ms |
21712 KB |
Output is correct |
4 |
Correct |
84 ms |
21844 KB |
Output is correct |
5 |
Correct |
176 ms |
25720 KB |
Output is correct |
6 |
Correct |
162 ms |
25848 KB |
Output is correct |
7 |
Correct |
307 ms |
26360 KB |
Output is correct |
8 |
Correct |
182 ms |
25464 KB |
Output is correct |
9 |
Correct |
151 ms |
26372 KB |
Output is correct |
10 |
Correct |
167 ms |
33776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
21380 KB |
Output is correct |
2 |
Correct |
55 ms |
20648 KB |
Output is correct |
3 |
Correct |
139 ms |
27040 KB |
Output is correct |
4 |
Correct |
121 ms |
25012 KB |
Output is correct |
5 |
Correct |
276 ms |
36216 KB |
Output is correct |
6 |
Correct |
223 ms |
29816 KB |
Output is correct |
7 |
Correct |
284 ms |
36436 KB |
Output is correct |
8 |
Correct |
221 ms |
30200 KB |
Output is correct |
9 |
Correct |
216 ms |
28920 KB |
Output is correct |
10 |
Correct |
213 ms |
28632 KB |
Output is correct |