#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
typedef pair<pii, pii> T;
T points[MAX];
int getind(vector<int>& v, int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin();
}
pii hor[MAX * 2];
int hmx[MAX * 2];
int hmn[MAX * 2];
vector<int> hpoint[MAX * 2];
vector<pii> hline[MAX];
pii ver[MAX * 2];
int vmx[MAX * 2];
int vmn[MAX * 2];
vector<int> vpoint[MAX * 2];
vector<pii> vline[MAX];
int dist[MAX];
struct segtree {
vector<set<pii>> tree;
int N;
segtree(int N) :N(N) { tree.resize(N * 4 + 10); }
void upd(int s, int e, int l, int r, pii x, int loc = 1) {
if (e < l || r < s) return;
if (l <= s && e <= r) {
tree[loc].insert(x);
return;
}
int m = (s + e) >> 1;
upd(s, m, l, r, x, loc * 2);
upd(m + 1, e, l, r, x, loc * 2 + 1);
}
void addq(int s, int e, int x, int mn, int mx, vector<int>& q, int loc = 1) {
if (e < x || x < s) return;
while (1) {
auto it = tree[loc].lower_bound(pii(mn, -1));
if (it == tree[loc].end()) break;
if (it->first > mx) break;
q.push_back(it->second);
tree[loc].erase(it);
}
if (s == e) return;
int m = (s + e) >> 1;
addq(s, m, x, mn, mx, q, loc * 2);
addq(m + 1, e, x, mn, mx, q, loc * 2 + 1);
}
void upd(int l, int r, pii x) { upd(0, N, l, r, x); }
void addq(int x, int mn, int mx, vector<int>& q) { addq(0, N, x, mn, mx, q); }
};
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int N;
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
cin >> N;
int i;
vector<int> Xs, Ys;
for (i = 1; i <= N; i++) {
cin >> points[i].first.first >> points[i].second.first >> points[i].first.second >> points[i].second.second;
Xs.push_back(points[i].first.first);
Xs.push_back(points[i].second.first);
Ys.push_back(points[i].first.second);
Ys.push_back(points[i].second.second);
}
Xs.push_back(sx);
Xs.push_back(ex);
Ys.push_back(sy);
Ys.push_back(ey);
Xs.push_back(0);
Ys.push_back(0);
Xs.push_back(1000000001);
Ys.push_back(1000000001);
sort(Xs.begin(), Xs.end());
sort(Ys.begin(), Ys.end());
Xs.erase(unique(Xs.begin(), Xs.end()), Xs.end());
Ys.erase(unique(Ys.begin(), Ys.end()), Ys.end());
int H, W;
H = Ys.size();
W = Xs.size();
sx = getind(Xs, sx);
ex = getind(Xs, ex);
sy = getind(Ys, sy);
ey = getind(Ys, ey);
for (i = 1; i <= N; i++) {
points[i].first.first = getind(Xs, points[i].first.first);
points[i].second.first = getind(Xs, points[i].second.first);
points[i].first.second = getind(Ys, points[i].first.second);
points[i].second.second = getind(Ys, points[i].second.second);
}
int HS, VS;
int cnt;
cnt = 0;
hor[++cnt] = pii(sx, sy);
hor[++cnt] = pii(ex, ey);
for (i = 1; i <= N; i++) hor[++cnt] = points[i].first, hor[++cnt] = points[i].second;
for (i = 1; i <= cnt; i++) hpoint[hor[i].first].push_back(i);
for (i = 1; i <= N; i++) hline[points[i].first.first].emplace_back(points[i].first.second, points[i].second.second), hline[points[i].second.first].emplace_back(points[i].first.second, points[i].second.second);
set<pii> st;
for (i = 0; i < W; i++) {
for (auto v : hpoint[i]) st.emplace(hor[v].second, v);
for (auto& [l, r] : hline[i]) {
while (1) {
auto it = st.upper_bound(pii(l, 1e9));
if (it == st.end()) break;
if (hor[it->second].second >= r) break;
else {
hmx[it->second] = i;
st.erase(it);
}
}
}
}
for (auto& [_, v] : st) hmx[v] = W - 1;
st.clear();
for (i = W - 1; i >= 0; i--) {
for (auto v : hpoint[i]) st.emplace(hor[v].second, v);
for (auto& [l, r] : hline[i]) {
while (1) {
auto it = st.upper_bound(pii(l, 1e9));
if (it == st.end()) break;
if (hor[it->second].second >= r) break;
else {
hmn[it->second] = i;
st.erase(it);
}
}
}
}
for (auto& [_, v] : st) hmn[v] = 0;
st.clear();
HS = cnt;
segtree hors(W + 1);
for (i = 2; i <= cnt; i++) hors.upd(hmn[i], hmx[i], pii(hor[i].second, i));
cnt = 0;
ver[++cnt] = pii(sx, sy);
ver[++cnt] = pii(ex, ey);
for (i = 1; i <= N; i++) ver[++cnt] = points[i].first, ver[++cnt] = points[i].second;
for (i = 1; i <= cnt; i++) vpoint[ver[i].second].push_back(i);
for (i = 1; i <= N; i++) vline[points[i].first.second].emplace_back(points[i].first.first, points[i].second.first), hline[points[i].second.second].emplace_back(points[i].first.first, points[i].second.first);
for (i = 0; i < H; i++) {
for (auto v : vpoint[i]) st.emplace(ver[v].first, v);
for (auto& [l, r] : vline[i]) {
while (1) {
auto it = st.upper_bound(pii(l, 1e9));
if (it == st.end()) break;
if (ver[it->second].first >= r) break;
else {
vmx[it->second] = i;
st.erase(it);
}
}
}
}
for (auto& [_, v] : st) vmx[v] = H - 1;
st.clear();
for (i = H - 1; i >= 0; i--) {
for (auto v : vpoint[i]) st.emplace(hor[v].first, v);
for (auto& [l, r] : vline[i]) {
while (1) {
auto it = st.upper_bound(pii(l, 1e9));
if (it == st.end()) break;
if (ver[it->second].first >= r) break;
else {
vmn[it->second] = i;
st.erase(it);
}
}
}
}
for (auto& [_, v] : st) vmn[v] = 0;
VS = cnt;
segtree vers(H + 1);
for (i = 2; i <= cnt; i++) vers.upd(vmn[i], vmx[i], pii(ver[i].first, i + HS));
if (sy == ey) {
if (ex <= hmx[1]) {
cout << 1 << ln;
return 0;
}
}
if (sx == ex) {
if (ey <= vmx[1]) {
cout << 1 << ln;
return 0;
}
}
queue<int> q;
q.push(1);
q.push(HS + 1);
vector<int> nxt;
while (q.size()) {
int t = q.front();
q.pop();
if (t == HS + 2 || t == 2) {
cout << dist[t] + 1 << ln;
return 0;
}
if (t > HS) hors.addq(ver[t - HS].first, vmn[t - HS], vmx[t - HS], nxt);
else vers.addq(hor[t].second, hmn[t], hmx[t], nxt);
for (auto v : nxt) dist[v] = dist[t] + 1, q.push(v);
nxt.clear();
}
}
Compilation message
golf.cpp: In function 'int main()':
golf.cpp:103:10: warning: variable 'VS' set but not used [-Wunused-but-set-variable]
103 | int HS, VS;
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
28628 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28628 KB |
Output is correct |
| 3 |
Correct |
15 ms |
28688 KB |
Output is correct |
| 4 |
Correct |
16 ms |
28884 KB |
Output is correct |
| 5 |
Incorrect |
24 ms |
30288 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
28628 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28628 KB |
Output is correct |
| 3 |
Correct |
15 ms |
28688 KB |
Output is correct |
| 4 |
Correct |
16 ms |
28884 KB |
Output is correct |
| 5 |
Incorrect |
24 ms |
30288 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
28628 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28628 KB |
Output is correct |
| 3 |
Correct |
15 ms |
28688 KB |
Output is correct |
| 4 |
Correct |
16 ms |
28884 KB |
Output is correct |
| 5 |
Incorrect |
24 ms |
30288 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
