#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 300000
#define M 300000
#define INF 0x3f3f3f3f
int abs_(int a) { return a > 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N], yy[N], xx_[N], yy_[N], n;
int tt[M], ii[M], ans[M], m;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[ii[j]] - yy[i_];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int ll[N], rr[N], *ej[N], eo[N], n_;
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
void delete_(int i, int j) {
int o;
for (o = eo[i]; o--; )
if (ej[i][o] == j) {
eo[i]--;
while (o < eo[i])
ej[i][o] = ej[i][o + 1], o++;
return;
}
}
int sz[N], c;
void dfs1(int p, int i) {
int o, centroid;
sz[i] = 1, centroid = 1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs1(i, j);
if (sz[j] * 2 > n_)
centroid = 0;
sz[i] += sz[j];
}
}
if ((n_ - sz[i]) * 2 > n_)
centroid = 0;
if (centroid)
c = i;
}
int ii_[N], dd[N], oo[N];
void dfs2(int p, int i, int o_) {
int o, p_, i_, y;
if (p == -1)
for (i_ = ll[i]; i_ <= rr[i]; i_++)
ii_[i_] = i_ - ll[i], dd[i_] = 0;
else
for (i_ = ll[i]; i_ <= rr[i]; i_++) {
y = yy[i_];
if (y < yy[ll[p]])
p_ = ll[p];
else if (y > yy[rr[p]])
p_ = rr[p];
else
p_ = ll[p] + y - yy[ll[p]];
ii_[i_] = ii_[p_], dd[i_] = dd[p_] + 1 + abs_(y - yy[p_]);
}
for (i_ = ll[i]; i_ <= rr[i]; i_++)
oo[i_] = o_;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs2(i, j, p == -1 ? o : o_);
}
}
void update(int *ft, int i, int n, int x) {
while (i < n) {
ft[i] = min(ft[i], x);
i |= i + 1;
}
}
int query(int *ft, int i) {
int x = INF;
while (i >= 0) {
x = min(x, ft[i]);
i &= i + 1, i--;
}
return x;
}
void cd(int *hh, int m, int n, int i) {
static int ft1[N], ft2[N], kk[N], hh_[M];
int m_, o, h, h_, i_, d, d_;
n_ = n, dfs1(-1, i), i = c;
dfs2(-1, i, -1);
memset(ft1, 0x3f, (rr[i] - ll[i] + 1) * sizeof *ft1);
memset(ft2, 0x3f, (rr[i] - ll[i] + 1) * sizeof *ft2);
for (h = 0; h < m; h++) {
h_ = hh[h], i_ = ii_[ii[h_]], d = dd[ii[h_]];
if (tt[h_] == 1)
update(ft1, i_, n, d - i_), update(ft2, rr[i] - ll[i] - i_, n, d + i_);
else {
if ((d_ = query(ft1, i_)) != INF)
ans[h_] = min(ans[h_], d + d_ + i_);
if ((d_ = query(ft2, rr[i] - ll[i] - i_)) != INF)
ans[h_] = min(ans[h_], d + d_ - i_);
}
}
memset(kk, 0, (eo[i] + 1) * sizeof *kk);
for (h = 0; h < m; h++) {
h_ = hh[h], o = oo[ii[h_]];
if (o != -1)
kk[o + 1]++;
}
for (o = 1; o < eo[i]; o++)
kk[o] += kk[o - 1];
m_ = 0;
for (h = 0; h < m; h++) {
h_ = hh[h], o = oo[ii[h_]];
if (o != -1)
hh_[kk[o]++] = h_, m_++;
}
memcpy(hh, hh_, (m = m_) * sizeof *hh_);
for (o = 0, h = 0; o < eo[i]; o++) {
int j = ej[i][o];
delete_(j, i);
h_ = h;
while (h_ < m && oo[ii[hh[h_]]] == o)
h_++;
cd(hh + h, h_ - h, sz[j] < sz[i] ? sz[j] : n - sz[i], j);
}
}
int main() {
static int hh[M];
int h, i, i_, j, j_, x, y, lower, upper;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
for (i = 0; i < n; i++)
ii[i] = i;
sort(ii, 0, n);
for (i = 0; i < n; i++)
xx_[i] = xx[ii[i]], yy_[i] = yy[ii[i]];
memcpy(xx, xx_, n * sizeof *xx_), memcpy(yy, yy_, n * sizeof *yy_);
n_ = 0;
for (i = 0; i < n; i = j) {
j = i + 1;
while (j < n && xx[j] == xx[j - 1] && yy[j] == yy[j - 1] + 1)
j++;
for (h = i; h < j; h++)
ii[h] = n_;
ll[n_] = i, rr[n_] = j - 1, n_++;
}
for (i = 0; i < n_; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (i = 0, j = 0; i < n; i++) {
x = xx[i], y = yy[i];
while (j < n && (xx[j] < x + 1 || xx[j] == x + 1 && yy[j] < y))
j++;
if (j < n && xx[j] == x + 1 && yy[j] == y) {
i_ = ii[i], j_ = ii[j];
if (ll[i_] == i || ll[j_] == j)
append(i_, j_), append(j_, i_);
}
}
scanf("%d", &m);
for (h = 0; h < m; h++) {
scanf("%d%d%d", &tt[h], &x, &y);
lower = -1, upper = n;
while (upper - lower > 1) {
i = (lower + upper) / 2;
if (xx[i] < x || xx[i] == x && yy[i] <= y)
lower = i;
else
upper = i;
}
ii[h] = lower;
}
memset(ans, 0x3f, m * sizeof *ans);
for (h = 0; h < m; h++)
hh[h] = h;
cd(hh, m, n_, 0);
for (h = 0; h < m; h++)
if (tt[h] == 2)
printf("%d\n", ans[h] == INF ? -1 : ans[h]);
return 0;
}
Compilation message
C.c: In function 'append':
C.c:48:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
48 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
C.c: In function 'main':
C.c:204:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
204 | while (j < n && (xx[j] < x + 1 || xx[j] == x + 1 && yy[j] < y))
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~
C.c:218:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
218 | if (xx[i] < x || xx[i] == x && yy[i] <= y)
| ~~~~~~~~~~~^~~~~~~~~~~~~
C.c:182:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
182 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
C.c:184:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
184 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
C.c:212:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
212 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
C.c:214:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
214 | scanf("%d%d%d", &tt[h], &x, &y);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
23636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
25840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
22876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
