#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }
static unsigned char str[5500055], *p=str;
const int MAXN = 100005;
const int MAXK = MAXN;
static int _int[MAXN*5], *_intp = _int;
inline int* newint(const unsigned int c) {
_intp += c;
return _intp - c;
}
struct BIT {
int *d, n;
void init(int _n) {
n = _n + 2;
d = newint(n);
fill(d, d+n, INF);
}
void upd(int x, int r) {
for(x++; x < n; x += rb(x))
if(r < d[x]) d[x] = r;
}
int get(int x) {
int r = INF; for(x++; x; x -= rb(x))
if(d[x] < r) r = d[x];
return r;
}
};
struct NOD {
NOD() : sy(INF), ey(-INF) {}
BIT bitu, bitd;
int x, sy, ey;
void init() {
int l = ey-sy+1;
bitu.init(l);
bitd.init(l);
}
void add(pii p) {
x = p.first;
if(p.second < sy) sy = p.second;
if(ey < p.second) ey = p.second;
}
void add(int y, int d) {
bitu.upd(y-sy, d-y);
bitd.upd(ey-y, d+y);
}
int get(int y) {
return min(bitu.get(y-sy) + y, bitd.get(ey-y) - y);
}
} nod[MAXK];
vector<int> T[MAXN], G[MAXK];
int P[17][MAXK];
int C[17][MAXN], CY[17][MAXN];
int D[MAXK], prt[MAXK], cnt[MAXK];
pii A[MAXN];
int B[MAXN];
int N, Q, K;
int getidx(const pii &p) {
int r = int(lower_bound(A+1, A+N+1, p) - A);
return r <= N && p == A[r] ? r : 0;
}
void predfs(int i) {
cnt[i] = 1;
for(int v : G[i]) if(!cnt[v]) {
predfs(v);
cnt[i] += cnt[v];
}
}
void cent(int &rt) {
int N = cnt[rt];
for(int hi, hc;;) {
hi = hc = -1;
for(int v : G[rt]) {
if(N <= cnt[v] || cnt[v] <= hc) continue;
hi = v; hc = cnt[v];
}
if(hc*2 <= N) break;
cnt[rt] = N - hc;
cnt[hi] = N;
rt = hi;
}
}
int makeCD(int i, int d) {
cent(i);
D[i] = d; P[d][i] = i;
queue<int> PQ;
for(int j = getidx({nod[i].x, nod[i].sy});; j++) {
if(N < j || A[j].first != nod[i].x) break;
PQ.push(j);
C[d][j] = 0;
CY[d][j] = A[j].second;
}
for(int j, c; !PQ.empty(); PQ.pop()) {
j = PQ.front();
c = C[d][j] + 1;
for(int v : T[j]) {
if(cnt[B[j]] < cnt[B[v]] || C[d][v] <= c) continue;
PQ.push(v);
C[d][v] = c;
CY[d][v] = CY[d][j];
}
}
for(int v : G[i]) if(cnt[v] < cnt[i]) {
v = makeCD(v, d+1);
prt[v] = i;
}
return i;
}
void makeTree() {
K = B[1] = 1;
nod[1].add(A[1]);
for(int i = 2, j; i <= N; i++) {
if(A[i-1].first != A[i].first || A[i-1].second != A[i].second-1) K++;
else fg(T, i-1, i);
B[i] = K;
nod[K].add(A[i]);
j = getidx({A[i].first-1, A[i].second});
if(j) {
fg(T, j, i);
fg(G, B[j], B[i]);
}
}
for(int i = 1; i <= K; i++) {
nod[i].init();
sorv(G[i]);
univ(G[i]);
}
}
void upd(int i) {
for(int v = B[i], d = D[v]; v; v = prt[v], d--)
nod[v].add(CY[d][i], C[d][i]);
}
int get(int i) {
int r = INF;
for(int v = B[i], d = D[v], t; v; v = prt[v], d--) {
t = nod[v].get(CY[d][i]) + C[d][i];
if(t < r) r = t;
}
return N <= r ? -1 : r;
}
int main() {
fread(str, 1, 5500055, stdin);
rf(N)
for(int i = 1; i <= N; i++) { rf(A[i].first) rf(A[i].second) }
sort(A+1, A+N+1);
makeTree();
predfs(1);
fill(C[0], C[16]+MAXN, INF);
makeCD(1, 0);
rf(Q)
for(int t, x, y; Q--;) {
rf(t) rf(x) rf(y)
x = getidx({x, y});
if(1 == t) upd(x);
else printf("%d\n", get(x));
}
return 0;
}
Compilation message
C.cpp: In function 'int main()':
C.cpp:168:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(str, 1, 5500055, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16384 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16512 KB |
Output is correct |
| 3 |
Execution timed out |
2067 ms |
16384 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16384 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16512 KB |
Output is correct |
| 3 |
Execution timed out |
2067 ms |
16384 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
93 ms |
25568 KB |
Output is correct |
| 2 |
Correct |
231 ms |
45792 KB |
Output is correct |
| 3 |
Correct |
199 ms |
35804 KB |
Output is correct |
| 4 |
Correct |
207 ms |
35720 KB |
Output is correct |
| 5 |
Correct |
209 ms |
41212 KB |
Output is correct |
| 6 |
Correct |
217 ms |
41060 KB |
Output is correct |
| 7 |
Correct |
204 ms |
30968 KB |
Output is correct |
| 8 |
Correct |
112 ms |
26492 KB |
Output is correct |
| 9 |
Correct |
79 ms |
25044 KB |
Output is correct |
| 10 |
Correct |
258 ms |
30840 KB |
Output is correct |
| 11 |
Correct |
128 ms |
26360 KB |
Output is correct |
| 12 |
Correct |
80 ms |
25044 KB |
Output is correct |
| 13 |
Correct |
87 ms |
24252 KB |
Output is correct |
| 14 |
Correct |
80 ms |
24312 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
750 ms |
72180 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16384 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16512 KB |
Output is correct |
| 3 |
Execution timed out |
2067 ms |
16384 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
