#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
struct cpnt{
int p, y, d;
cpnt() {}
cpnt(int p, int y, int d) : p(p), y(y), d(d) {}
};
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];
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, vector <cpnt> &X)
{
vector <cpnt> Y;
int i, x, y;
for(i=L[p]; i<=R[p]; i++){
K[H[p] + i - L[p]].push_back(X[i - L[p]]);
}
for(int &t: V[p]){
if(t != r && !chk[t]){
Y.clear();
for(i=L[t]; i<=R[t]; i++){
y = min(max(P[H[t] + i - L[t]].second, L[p]), R[p]);
x = abs(y - P[H[t] + i - L[t]].second) + X[y - L[p]].d + 1;
Y.emplace_back(c, X[y - L[p]].y, x);
}
dfs2(c, t, p, Y);
}
}
}
void dnc(int p)
{
vector <cpnt> X;
int i, s;
s = dfs1(p, 0);
for(; ; ){
for(i=V[p].size()-1; i>=0; i--){
if(S[V[p][i]] < S[p] && S[V[p][i]] * 2 >= s){
p = V[p][i]; break;
}
}
if(i < 0) break;
}
printf("%d\n", p);
chk[p] = 1;
for(i=L[p]; i<=R[p]; i++){
X.emplace_back(p, i, 0);
}
dfs2(p, p, 0, X);
for(int &t: V[p]){
if(!chk[t]){
dnc(t);
}
}
}
void query1(int p)
{
int y;
for(cpnt &t: K[p]){
T1.update(H[t.p] + t.y - L[t.p], t.d - t.y);
T2.update(H[t.p] + t.y - L[t.p], t.d + t.y);
}
}
int query2(int p)
{
int ret;
ret = 1e9;
for(cpnt &t: K[p]){
ret = min(ret, t.d + T1.get_min(H[t.p], H[t.p] + t.y - L[t.p]) + t.y);
ret = min(ret, t.d + T2.get_min(H[t.p] + t.y - L[t.p], H[t.p] + R[t.p] - L[t.p]) - t.y);
}
return ret < 1e8? ret : -1;
}
int main()
{
vector <int> X, Y;
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 query1(int)':
C.cpp:136:6: warning: unused variable 'y' [-Wunused-variable]
int y;
^
C.cpp: In function 'int main()':
C.cpp:184:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0, l=0; j<X.size() && l<Y.size(); ){
~^~~~~~~~~
C.cpp:184:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0, l=0; j<X.size() && l<Y.size(); ){
~^~~~~~~~~
C.cpp:163:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
C.cpp:166: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:199:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
C.cpp:202: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 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
153 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
395 ms |
32616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
