#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
struct cpnt{
int p, d, l, r;
cpnt() {}
cpnt(int p, int d, int l, int r) : p(p), d(d), l(l), r(r) {}
};
struct minseg{
int T[303030];
int sz = 1 << 17;
minseg()
{
int i;
for(i=0; i<sz+sz; i++){
T[i] = 1e9;
}
}
void update(int p, int v)
{
p += sz;
T[p] = min(T[p], v);
for(p>>=1; p; p>>=1){
T[p] = min(T[p << 1], T[p << 1 | 1]);
}
}
int get_min(int l, int r)
{
int ret = 1e9;
l += sz; r += sz;
for(; l<r; ){
if(l & 1) ret = min(ret, T[l]);
if(~r & 1) ret = min(ret, T[r]);
l = l + 1 >> 1;
r = r - 1 >> 1;
}
if(l == r){
ret = min(ret, T[l]);
}
return ret;
}
};
vector <pii> P;
vector <int> V[101010], X, Y;
vector <cpnt> K[101010];
minseg T1, T2;
int L[101010], R[101010], H[101010];
int S[101010], D[101010];
bool chk[101010];
int n, k;
int dfs1(int p, int r)
{
S[p] = 1;
for(int &t: V[p]){
if(t != r && !chk[t]){
S[p] += dfs1(t, p);
}
}
return S[p];
}
void dfs2(int c, int p, int r, int d, int s, int e)
{
K[p].emplace_back(c, d, s, e);
for(int &t: V[p]){
if(t != r && !chk[t]){
dfs2(c, t, p, d + 1, min(max(s, L[t]), R[t]), max(min(e, R[t]), L[t]));
}
}
}
void dnc(int p)
{
int i, s;
s = dfs1(p, 0);
for(; ; ){
for(i=0; i<V[p].size(); i++){
if(S[V[p][i]] < S[p] && S[V[p][i]] * 2 >= s){
p = V[p][i]; break;
}
}
if(i == V[p].size()) break;
}
chk[p] = 1;
dfs2(p, p, 0, 0, L[p], R[p]);
for(int &t: V[p]){
if(!chk[t]){
dnc(t);
}
}
}
void query1(int p)
{
int y;
for(cpnt &t: K[D[p]]){
y = min(max(P[p].second, t.l), t.r);
T1.update(H[t.p] + y - L[t.p], (t.d + abs(P[p].second - y)) - (y - L[t.p]));
T2.update(H[t.p] + y - L[t.p], (t.d + abs(P[p].second - y)) + (y - L[t.p]));
}
}
int query2(int p)
{
int y, ret;
ret = 1e9;
for(cpnt &t: K[D[p]]){
y = min(max(P[p].second, t.l), t.r);
ret = min(ret, t.d + abs(P[p].second - y) +
T1.get_min(H[t.p], H[t.p] + y - L[t.p]) + (y - L[t.p]));
ret = min(ret, t.d + abs(P[p].second - y) +
T2.get_min(H[t.p] + y - L[t.p], H[t.p] + R[t.p] - L[t.p]) - (y - L[t.p]));
}
return ret < 1e8? ret : -1;
}
int main()
{
int q, i, j, l, x, y, t;
scanf("%d", &n);
for(i=0; i<n; i++){
scanf("%d%d", &x, &y);
P.emplace_back(x, y);
}
sort(P.begin(), P.end());
for(i=0; i<n; ){
for(j=i; j<n && P[i].first == P[j].first; j=l){
k ++;
for(l=j; l<n && P[j].first == P[l].first && P[j].second == P[l].second - l + j; l++){
D[l] = k;
}
L[k] = P[j].second; R[k] = P[l - 1].second; H[k] = j;
X.push_back(k);
}
i = j;
for(j=0, l=0; j<X.size() && l<Y.size(); ){
if(max(L[X[j]], L[Y[l]]) <= min(R[X[j]], R[Y[l]])){
V[X[j]].push_back(Y[l]);
V[Y[l]].push_back(X[j]);
}
if(R[X[j]] < R[Y[l]]) j ++;
else l ++;
}
swap(X, Y); X.clear();
}
dnc(1);
scanf("%d", &q);
for(; q--; ){
scanf("%d%d%d", &t, &x, &y);
i = lower_bound(P.begin(), P.end(), pii(x, y)) - P.begin();
if(t == 1) query1(i);
else printf("%d\n", query2(i));
}
return 0;
}
Compilation message
C.cpp: In member function 'int minseg::get_min(int, int)':
C.cpp:45:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
l = l + 1 >> 1;
~~^~~
C.cpp:46:10: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
r = r - 1 >> 1;
~~^~~
C.cpp: In function 'void dnc(int)':
C.cpp:97:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<V[p].size(); i++){
~^~~~~~~~~~~~
C.cpp:102:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i == V[p].size()) break;
~~^~~~~~~~~~~~~~
C.cpp: In function 'int main()':
C.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0, l=0; j<X.size() && l<Y.size(); ){
~^~~~~~~~~
C.cpp:169:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0, l=0; j<X.size() && l<Y.size(); ){
~^~~~~~~~~
C.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
C.cpp:151:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
C.cpp:184:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
C.cpp:187:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &t, &x, &y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7168 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7168 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
7168 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7168 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7168 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
7168 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
8820 KB |
Output is correct |
| 2 |
Correct |
320 ms |
57948 KB |
Output is correct |
| 3 |
Incorrect |
273 ms |
23528 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2056 ms |
166356 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7168 KB |
Output is correct |
| 2 |
Correct |
8 ms |
7168 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
7168 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
