This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)
using namespace std;
const int Nmax = 2e5 + 5;
int X1, X2, Y1, Y2, n, limx, limy, StartV, StartH, FinishV, FinishH, ids;
int D[Nmax*4];
vector<int> allx, ally, start[Nmax], finish[Nmax];
vector< pair<int,int> > V[Nmax], H[Nmax];
vector<int> vec;
struct point
{
int x, y;
} S, F;
struct Node
{
int p, l, r, id;
};
vector<Node> segmV, segmH;
class SegmentTree
{
int a[Nmax<<2];
public:
int N;
void update(int node, int st, int dr, int pos, int add)
{
if(st == dr)
{
a[node] += add;
return;
}
if(pos <= mid) update(left_son, st, mid, pos, add);
else update(right_son, mid+1, dr, pos, add);
a[node] = a[left_son] + a[right_son];
}
int before(int node, int st, int dr, int pos)
{
if(!a[node]) return 1;
if(st == dr) return st;
if(dr <= pos)
{
int ans = before(right_son, mid+1, dr, pos);
if(ans == 1) ans = before(left_son, st, mid, pos);
return ans;
}
else
{
int ans = 1;
if(mid+1 <= pos) ans = before(right_son, mid+1, dr, pos);
if(ans == 1) ans = before(left_son, st, mid, pos);
return ans;
}
}
int after(int node, int st, int dr, int pos)
{
if(!a[node]) return N;
if(st == dr) return st;
if(st >= pos)
{
int ans = after(left_son, st, mid, pos);
if(ans == N) ans = after(right_son, mid+1, dr, pos);
return ans;
}
else
{
int ans = N;
if(pos <= mid) ans = after(left_son, st, mid, pos);
if(ans == N) ans = after(right_son, mid+1, dr, pos);
return ans;
}
}
} aint;
void read()
{
int i, X1, X2, Y1, Y2;
cin >> S.x >> S.y >> F.x >> F.y;
cin >> n;
for(i=0; i<n; ++i)
{
cin >> X1 >> X2 >> Y1 >> Y2;
allx.push_back(X1); allx.push_back(X2);
ally.push_back(Y1); ally.push_back(Y2);
}
}
void normalize()
{
map<int,int> mpx, mpy;
int X1, Y1, X2, Y2, i;
allx.push_back(S.x); allx.push_back(F.x);
ally.push_back(S.y); ally.push_back(F.y);
for(auto it : allx) mpx[it] = 1;
for(auto it : ally) mpy[it] = 1;
for(auto &it : mpx) it.second = ++limx;
for(auto &it : mpy) it.second = ++limy;
S.x = mpx[S.x]; S.y = mpy[S.y]; F.x = mpx[F.x]; F.y = mpy[F.y];
for(i=0; i<n; ++i)
{
X1 = mpx[allx[2*i]];
X2 = mpx[allx[2*i+1]];
Y1 = mpy[ally[2*i]];
Y2 = mpy[ally[2*i+1]];
V[X1].push_back({Y1, Y2});
V[X2].push_back({Y1, Y2});
H[Y1].push_back({X1, X2});
H[Y2].push_back({X1, X2});
}
V[S.x].push_back({S.y, S.y});
V[F.x].push_back({F.y, F.y});
H[S.y].push_back({S.x, S.x});
H[F.y].push_back({F.x, F.x});
}
void expand_vertically()
{
//aint.clear();
int i;
for(i=1; i<=limx; ++i) start[i].clear(), finish[i].clear();
for(i=1; i<=limy; ++i)
for(auto it : H[i])
if(it.first != it.second)
{
start[it.first].push_back(i);
finish[it.second].push_back(i);
}
aint.N = limy;
for(i=1; i<=limx; ++i)
{
for(auto it : finish[i]) aint.update(1, 1, limy, it, -1);
for(auto it : V[i])
{
int x, y;
x = aint.before(1, 1, limy, it.first);
y = aint.after(1, 1, limy, it.second);
segmV.push_back({i, x, y, ++ids});
if(it.first == it.second)
{
if(S.x == i && S.y == it.first) StartV = ids;
else if(F.x == i && F.y == it.first) FinishV = ids;
}
}
for(auto it : start[i]) aint.update(1, 1, limy, it, 1);
}
}
void expand_horizontally()
{
// aint.clear();
int i;
for(i=1; i<=limy; ++i) start[i].clear(), finish[i].clear();
for(i=1; i<=limx; ++i)
for(auto it : V[i])
if(it.first != it.second)
{
start[it.first].push_back(i);
finish[it.second].push_back(i);
}
aint.N = limx;
for(i=1; i<=limy; ++i)
{
for(auto it : finish[i]) aint.update(1, 1, limx, it, -1);
for(auto it : H[i])
{
int x, y;
x = aint.before(1, 1, limx, it.first);
y = aint.after(1, 1, limx, it.second);
segmH.push_back({i, x, y, ++ids});
if(it.first == it.second)
{
if(S.x == it.first && S.y == i) StartH = ids;
else if(F.x == it.first && F.y == i) FinishH = ids;
}
}
for(auto it : start[i]) aint.update(1, 1, limx, it, 1);
}
}
class Kawaii
{
set< pair<int,int> > s[Nmax<<2];
public:
void update(int node, int st, int dr, int L, int R, int pos, int id)
{
if(L <= st && dr <= R)
{
s[node].insert({pos, id});
return;
}
if(L <= mid) update(left_son, st, mid, L, R, pos, id);
if(mid < R) update(right_son, mid+1, dr, L, R, pos, id);
}
void take(int node, int l, int r)
{
set< pair<int,int> > :: iterator it, itt;
it = itt = s[node].lower_bound({l, 0});
while(it != s[node].end() && it->first <= r)
{
if(D[it->second] == -1) vec.push_back(it->second);
++it;
}
s[node].erase(itt, it);
}
void query(int node, int st, int dr, int L, int R, int P)
{
take(node, L, R);
if(st == dr) return;
if(P <= mid) query(left_son, st, mid, L, R, P);
else query(right_son, mid+1, dr, L, R, P);
}
} hor, ver;
void create_tree()
{
for(auto it : segmV)
ver.update(1, 1, limy, it.l, it.r, it.p, it.id);
for(auto it : segmH)
hor.update(1, 1, limx, it.l, it.r, it.p, it.id);
}
void vecini(int node)
{
vec.clear();
if(node <= 2*n + 2) /// vertical
{
Node act = segmV[node-1];
hor.query(1, 1, limx, act.l, act.r, act.p);
}
else
{
Node act = segmH[node-1-(2*n+2)];
ver.query(1, 1, limy, act.l, act.r, act.p);
}
}
void bfs()
{
int node, i;
queue<int> q;
for(i=1; i<=ids; ++i) D[i] = -1;
D[StartV] = D[StartH] = 0;
q.push(StartV); q.push(StartH);
while(q.size())
{
node = q.front();
q.pop();
vecini(node);
for(auto it : vec)
{
D[it] = D[node] + 1;
q.push(it);
}
}
int ans = 1e9;
for(auto it : segmV)
if(F.x == it.p && it.l<=F.y && F.y<=it.r)
ans = min(ans, D[it.id] + 1);
for(auto it : segmH)
if(F.y == it.p && it.l<=F.x && F.x<=it.r)
ans = min(ans, D[it.id]+1);
cout << ans << '\n';
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false);
read();
normalize();
expand_vertically();
expand_horizontally();
create_tree();
bfs();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |