#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int INF = 5e7;
int N;
pii A[MAXN+10];
vector<int> X[MAXN+10], Y[MAXN+10];
struct Line
{
int l, r, p;
Line(int l, int r, int p) : l(l), r(r), p(p) {}
bool operator < (const Line &q) const { return r<q.r; }
};
int Q;
vector<Line> LX[MAXN+10], LY[MAXN+10];
vector<int> adjX[MAXN+10], adjY[MAXN+10];
pii get(int y, int x)
{
int nx=lower_bound(LX[y].begin(), LX[y].end(), Line(0, x, 0))->p;
int ny=lower_bound(LY[x].begin(), LY[x].end(), Line(0, y, 0))->p;
return {nx, ny};
}
pii P[MAXN+10];
struct Tree
{
int M;
//vector<vector<int>> adj, cdist;
//vector<int> sz, del, cpar, cdep;
int sz[MAXN+10], del[MAXN+10], cpar[MAXN+10], cdist[MAXN+10][30], cdep[MAXN+10];
vector<int> adj[MAXN+10];
Tree()
{
M=0;
memset(sz, 0, sizeof(sz));
memset(del, 0, sizeof(del));
memset(cpar, 0, sizeof(cpar));
memset(cdist, 0, sizeof(cdist));
memset(cdep, 0, sizeof(cdep));
//sz=del=cpar=cdep=vector<int>(MAXN+10);
//cdist.resize(MAXN+10);
//for(auto &it : cdist) it.resize(30);
//adj.resize(MAXN+10);
}
void getsz(int now, int bef)
{
sz[now]=1;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(del[nxt]) continue;
getsz(nxt, now);
sz[now]+=sz[nxt];
}
}
int getcen(int now, int bef, int S)
{
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(del[nxt]) continue;
if(sz[nxt]>S/2) return getcen(nxt, now, S);
}
return now;
}
void dfs(int now, int bef, int t, int dist)
{
cdist[now][t]=dist;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(del[nxt]) continue;
dfs(nxt, now, t, dist+1);
}
}
void decomp(int now, int bef, int cendep)
{
getsz(now, now);
now=getcen(now, now, sz[now]/2);
cpar[now]=bef;
cdep[now]=cendep;
dfs(now, now, cendep, 0);
del[now]=true;
for(auto nxt : adj[now])
{
if(del[nxt]) continue;
decomp(nxt, now, cendep+1);
}
}
void init()
{
decomp(1, 0, 1);
//for(int i=1; i<=M; i++) assert(del[i]);
}
vector<int> getpar(int now)
{
vector<int> ans;
while(now)
{
ans.push_back(now);
now=cpar[now];
}
return ans;
}
}TX, TY;
vector<pii> TP1;
vector<int> TP2;
int main()
{
scanf("%d", &N);
for(int i=1; i<=N; i++)
{
int y, x;
scanf("%d%d", &y, &x);
A[i]={y, x};
X[y].push_back(x);
Y[x].push_back(y);
}
for(int i=1; i<=MAXN; i++)
{
if(X[i].empty()) continue;
sort(X[i].begin(), X[i].end());
int bef=X[i][0];
for(int j=0; j+1<X[i].size(); j++)
{
if(X[i][j]+1<X[i][j+1])
{
LX[i].push_back({bef, X[i][j], ++TX.M});
//printf("LX %d %d %d %d\n", i, LX[i].back().l, LX[i].back().r, LX[i].back().p);
bef=X[i][j+1];
}
}
LX[i].push_back({bef, X[i].back(), ++TX.M});
//printf("LX %d %d %d %d\n", i, LX[i].back().l, LX[i].back().r, LX[i].back().p);
}
/*
int cnt=0;
for(int i=2; i<=MAXN; i++)
{
int p=0;
for(auto it : LX[i])
{
for(; p<LX[i-1].size() && LX[i-1][p].r<it.l; p++);
for(; p<LX[i-1].size() && LX[i-1][p].l<=it.r; p++)
{
int u=LX[i-1][p].p, v=it.p;
TX.adj[u].push_back(v);
TX.adj[v].push_back(u);
cnt++;
//printf("adjX %d %d\n", u, v);
}
if(p) p--;
}
}
*/
for(int i=1; i<TX.M; i++)
{
int u=i, v=i+1;
TX.adj[u].push_back(v);
TX.adj[v].push_back(u);
}
//assert(cnt==TX.M-1);
for(int i=1; i<=MAXN; i++)
{
if(Y[i].empty()) continue;
sort(Y[i].begin(), Y[i].end());
int bef=Y[i][0];
for(int j=0; j+1<Y[i].size(); j++)
{
if(Y[i][j]+1!=Y[i][j+1])
{
LY[i].push_back({bef, Y[i][j], ++TY.M});
//printf("LY %d %d %d %d\n", i, LY[i].back().l, LY[i].back().r, LY[i].back().p);
bef=Y[i][j+1];
}
}
LY[i].push_back({bef, Y[i].back(), ++TY.M});
//printf("LY %d %d %d %d\n", i, LY[i].back().l, LY[i].back().r, LY[i].back().p);
}
/*
cnt=0;
for(int i=2; i<=MAXN; i++)
{
int p=0;
for(auto it : LY[i])
{
for(; p<LY[i-1].size() && LY[i-1][p].r<it.l; p++);
for(; p<LY[i-1].size() && LY[i-1][p].l<=it.r; p++)
{
int u=LY[i-1][p].p, v=it.p;
TY.adj[u].push_back(v);
TY.adj[v].push_back(u);
cnt++;
//printf("adjY %d %d\n", u, v);
}
if(p) p--;
}
}
assert(cnt==TY.M-1);
*/
for(int i=1; i<TY.M; i++)
{
int u=i, v=i+1;
TY.adj[u].push_back(v);
TY.adj[v].push_back(u);
}
TX.init(); TY.init();
for(int i=1; i<=N; i++)
{
P[i]=get(A[i].first, A[i].second);
vector<int> V1=TX.getpar(P[i].first);
vector<int> V2=TY.getpar(P[i].second);
for(auto it : V1) for(auto jt : V2) TP1.push_back({it, jt});
}
sort(TP1.begin(), TP1.end());
TP1.erase(unique(TP1.begin(), TP1.end()), TP1.end());
TP2=vector<int>(TP1.size(), INF);
scanf("%d", &Q);
bool flag=false;
while(Q--)
{
int tt, y, x;
scanf("%d%d%d", &tt, &y, &x);
pii t=get(y, x);
vector<int> V1=TX.getpar(t.first);
vector<int> V2=TY.getpar(t.second);
if(tt==1)
{
for(auto it : V1) for(auto jt : V2)
{
int pt=lower_bound(TP1.begin(), TP1.end(), pii(it, jt))-TP1.begin();
TP2[pt]=min(TP2[pt], TX.cdist[t.first][TX.cdep[it]]+TY.cdist[t.second][TY.cdep[jt]]);
}
flag=true;
}
else
{
if(!flag) { printf("-1\n"); continue; }
int ans=INF;
for(auto it : V1) for(auto jt : V2)
{
int pt=lower_bound(TP1.begin(), TP1.end(), pii(it, jt))-TP1.begin();
ans=min(ans, TX.cdist[t.first][TX.cdep[it]]+TY.cdist[t.second][TY.cdep[jt]]+TP2[pt]);
}
if(ans==INF) ans=-1;
//if(ans!=-1) assert(flag);
printf("%d\n", ans);
}
}
}
Compilation message
C.cpp: In function 'int main()':
C.cpp:146:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int j=0; j+1<X[i].size(); j++)
| ~~~^~~~~~~~~~~~
C.cpp:192:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for(int j=0; j+1<Y[i].size(); j++)
| ~~~^~~~~~~~~~~~
C.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
C.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
134 | scanf("%d%d", &y, &x);
| ~~~~~^~~~~~~~~~~~~~~~
C.cpp:245:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
245 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
C.cpp:250:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
250 | scanf("%d%d%d", &tt, &y, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
45688 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
45696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
45688 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
45696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
700 ms |
81112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
478 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
45688 KB |
Output is correct |
| 2 |
Incorrect |
27 ms |
45696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
