#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int s, t, u, v;
cin >> s >> t >> u >> v;
int n;
cin >> n;
vector<int> a(n), b(n), c(n), d(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> c[i] >> b[i] >> d[i];
}
vector<int> xs;
xs.push_back(s);
xs.push_back(t);
xs.push_back(u);
xs.push_back(v);
for (int i = 0; i < n; i++) {
xs.push_back(a[i]);
xs.push_back(b[i]);
xs.push_back(c[i]);
xs.push_back(d[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
s = (int) (lower_bound(xs.begin(), xs.end(), s) - xs.begin());
t = (int) (lower_bound(xs.begin(), xs.end(), t) - xs.begin());
u = (int) (lower_bound(xs.begin(), xs.end(), u) - xs.begin());
v = (int) (lower_bound(xs.begin(), xs.end(), v) - xs.begin());
for (int i = 0; i < n; i++) {
a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
b[i] = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
c[i] = (int) (lower_bound(xs.begin(), xs.end(), c[i]) - xs.begin());
d[i] = (int) (lower_bound(xs.begin(), xs.end(), d[i]) - xs.begin());
}
int k = (int) xs.size();
vector<array<int, 3>> ver;
vector<array<int, 3>> hor;
const int inf = (int) 1e9;
vector<int> mx(4 * k, 0);
vector<int> mn(4 * k, k - 1);
function<void(int, int, int, int, int, int)> Modify = [&](int x, int l, int r, int ll, int rr, int v) {
if (l > r || ll > rr || l > rr || r < ll) {
return;
}
if (ll <= l && r <= rr) {
mx[x] = max(mx[x], v);
mn[x] = min(mn[x], v);
return;
}
int mid = l + r >> 1;
if (rr <= mid) {
Modify(x << 1, l, mid, ll, rr, v);
} else if (ll > mid) {
Modify(x << 1 | 1, mid + 1, r, ll, rr, v);
} else {
Modify(x << 1, l, mid, ll, rr, v);
Modify(x << 1 | 1, mid + 1, r, ll, rr, v);
}
};
function<int(int, int, int, int)> QueryMin = [&](int x, int l, int r, int i) {
if (l == r) {
return mn[x];
}
int mid = l + r >> 1;
if (i <= mid) {
return min(QueryMin(x << 1, l, mid, i), mn[x]);
} else {
return min(QueryMin(x << 1 | 1, mid + 1, r, i), mn[x]);
}
};
function<int(int, int, int, int)> QueryMax = [&](int x, int l, int r, int i) {
if (l == r) {
return mx[x];
}
int mid = l + r >> 1;
if (i <= mid) {
return max(QueryMax(x << 1, l, mid, i), mx[x]);
} else {
return max(QueryMax(x << 1 | 1, mid + 1, r, i), mx[x]);
}
};
{
// left
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return b[i] < b[j];
});
vector<int> from(n);
vector<int> to(n);
set<pair<int, int>> st;
for (int i : order) {
while (!st.empty()) {
auto it = st.begin();
int idx = it->second;
if (d[idx] < b[i]) {
Modify(1, 0, k - 1, a[idx] + 1, c[idx] - 1, d[idx]);
st.erase(it);
} else {
break;
}
}
from[i] = QueryMax(1, 0, k - 1, a[i]);
st.emplace(d[i], i);
}
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
sort(order.begin(), order.end(), [&](int i, int j) {
return d[i] > d[j];
});
st.clear();
for (int i : order) {
while (!st.empty()) {
auto it = prev(st.end());
int idx = it->second;
if (b[idx] > d[i]) {
Modify(1, 0, k - 1, a[idx] + 1, c[idx] - 1, b[idx]);
st.erase(it);
} else {
break;
}
}
to[i] = QueryMin(1, 0, k - 1, a[i]);
st.emplace(b[i], i);
}
for (int i = 0; i < n; i++) {
ver.push_back({a[i], from[i], to[i]});
}
}
{
// right
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return b[i] < b[j];
});
vector<int> from(n);
vector<int> to(n);
set<pair<int, int>> st;
for (int i : order) {
while (!st.empty()) {
auto it = st.begin();
int idx = it->second;
if (d[idx] < b[i]) {
Modify(1, 0, k - 1, a[idx] + 1, c[idx] - 1, d[idx]);
st.erase(it);
} else {
break;
}
}
from[i] = QueryMax(1, 0, k - 1, c[i]);
st.emplace(d[i], i);
}
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
sort(order.begin(), order.end(), [&](int i, int j) {
return d[i] > d[j];
});
st.clear();
for (int i : order) {
while (!st.empty()) {
auto it = prev(st.end());
int idx = it->second;
if (b[idx] > d[i]) {
Modify(1, 0, k - 1, a[idx] + 1, c[idx] - 1, b[idx]);
st.erase(it);
} else {
break;
}
}
to[i] = QueryMin(1, 0, k - 1, c[i]);
st.emplace(b[i], i);
}
for (int i = 0; i < n; i++) {
ver.push_back({c[i], from[i], to[i]});
}
}
{
// bottom
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return a[i] < a[j];
});
vector<int> from(n);
vector<int> to(n);
set<pair<int, int>> st;
for (int i : order) {
while (!st.empty()) {
auto it = st.begin();
int idx = it->second;
if (c[idx] < a[i]) {
Modify(1, 0, k - 1, b[idx] + 1, d[idx] - 1, c[idx]);
st.erase(it);
} else {
break;
}
}
from[i] = QueryMax(1, 0, k - 1, b[i]);
st.emplace(c[i], i);
}
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
sort(order.begin(), order.end(), [&](int i, int j) {
return c[i] > c[j];
});
st.clear();
for (int i : order) {
while (!st.empty()) {
auto it = prev(st.end());
int idx = it->second;
if (a[idx] > c[i]) {
Modify(1, 0, k - 1, b[idx] + 1, d[idx] - 1, a[idx]);
st.erase(it);
} else {
break;
}
}
to[i] = QueryMin(1, 0, k - 1, b[i]);
st.emplace(a[i], i);
}
for (int i = 0; i < n; i++) {
hor.push_back({b[i], from[i], to[i]});
}
}
{
// top
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return a[i] < a[j];
});
vector<int> from(n);
vector<int> to(n);
set<pair<int, int>> st;
for (int i : order) {
while (!st.empty()) {
auto it = st.begin();
int idx = it->second;
if (c[idx] < a[i]) {
Modify(1, 0, k - 1, b[idx] + 1, d[idx] - 1, c[idx]);
st.erase(it);
} else {
break;
}
}
from[i] = QueryMax(1, 0, k - 1, d[i]);
st.emplace(c[i], i);
}
mx = vector<int>(4 * k, 0);
mn = vector<int>(4 * k, k - 1);
sort(order.begin(), order.end(), [&](int i, int j) {
return c[i] > c[j];
});
st.clear();
for (int i : order) {
while (!st.empty()) {
auto it = prev(st.end());
int idx = it->second;
if (a[idx] > c[i]) {
Modify(1, 0, k - 1, b[idx] + 1, d[idx] - 1, a[idx]);
st.erase(it);
} else {
break;
}
}
to[i] = QueryMin(1, 0, k - 1, d[i]);
st.emplace(a[i], i);
}
for (int i = 0; i < n; i++) {
hor.push_back({d[i], from[i], to[i]});
}
}
{
// start ver
int from = 0;
for (int i = 0; i < n; i++) {
if (d[i] < t && a[i] < s && s < c[i]) {
from = max(from, d[i]);
}
}
int to = k - 1;
for (int i = 0; i < n; i++) {
if (b[i] > t && a[i] < s && s < c[i]) {
to = min(to, b[i]);
}
}
ver.push_back({s, from, to});
}
{
// start hor
int from = 0;
for (int i = 0; i < n; i++) {
if (c[i] < s && b[i] < t && t < d[i]) {
from = max(from, c[i]);
}
}
int to = k - 1;
for (int i = 0; i < n; i++) {
if (a[i] > s && b[i] < t && t < d[i]) {
to = min(to, a[i]);
}
}
hor.push_back({t, from, to});
}
{
// end ver
int from = 0;
for (int i = 0; i < n; i++) {
if (d[i] < v && a[i] < u && u < c[i]) {
from = max(from, d[i]);
}
}
int to = k - 1;
for (int i = 0; i < n; i++) {
if (b[i] > v && a[i] < u && u < c[i]) {
to = min(to, b[i]);
}
}
ver.push_back({u, from, to});
}
{
// end hor
int from = 0;
for (int i = 0; i < n; i++) {
if (c[i] < u && b[i] < v && v < d[i]) {
from = max(from, c[i]);
}
}
int to = k - 1;
for (int i = 0; i < n; i++) {
if (a[i] > u && b[i] < v && v < d[i]) {
to = min(to, a[i]);
}
}
hor.push_back({v, from, to});
}
sort(hor.begin(), hor.end());
sort(ver.begin(), ver.end());
hor.erase(unique(hor.begin(), hor.end()), hor.end());
ver.erase(unique(ver.begin(), ver.end()), ver.end());
int sh = (int) hor.size();
int sv = (int) ver.size();
int m = sh + sv;
vector<int> dist(m, -1);
for (int i = 0; i < sh; i++) {
if (hor[i][0] == t && hor[i][1] <= s && s <= hor[i][2]) {
dist[i] = 1;
}
}
for (int i = 0; i < sv; i++) {
if (ver[i][0] == s && ver[i][1] <= t && t <= ver[i][2]) {
dist[sh + i] = 1;
}
}
vector<int> que;
for (int i = 0; i < m; i++) {
if (dist[i] == 1) {
que.push_back(i);
}
}
vector<set<pair<int, int>>> st_hor(4 * k);
vector<set<pair<int, int>>> st_ver(4 * k);
vector<int> qv;
function<void(int, int, int, int, int, int, pair<int, int>)> Insert = [&](int t, int x, int l, int r, int ll, int rr, pair<int, int> p) {
if (ll <= l && r <= rr) {
if (t == 0) {
st_hor[x].insert(p);
} else {
st_ver[x].insert(p);
}
return;
}
int mid = l + r >> 1;
if (rr <= mid) {
Insert(t, x << 1, l, mid, ll, rr, p);
} else if (ll > mid) {
Insert(t, x << 1 | 1, mid + 1, r, ll, rr, p);
} else {
Insert(t, x << 1, l, mid, ll, rr, p);
Insert(t, x << 1 | 1, mid + 1, r, ll, rr, p);
}
};
function<void(int, int, int, int, int, int, pair<int, int>)> Remove = [&](int t, int x, int l, int r, int ll, int rr, pair<int, int> p) {
if (ll <= l && r <= rr) {
if (t == 0) {
st_hor[x].erase(p);
} else {
st_ver[x].erase(p);
}
return;
}
int mid = l + r >> 1;
if (rr <= mid) {
Remove(t, x << 1, l, mid, ll, rr, p);
} else if (ll > mid) {
Remove(t, x << 1 | 1, mid + 1, r, ll, rr, p);
} else {
Remove(t, x << 1, l, mid, ll, rr, p);
Remove(t, x << 1 | 1, mid + 1, r, ll, rr, p);
}
};
function<void(int, int, int, int, int, int, int)> Query = [&](int t, int x, int l, int r, int i, int ll, int rr) {
if (t == 0) {
while (true) {
auto it = st_hor[x].lower_bound(make_pair(ll, -1));
if (it != st_hor[x].end() && it->first <= rr) {
int idx = it->second;
qv.push_back(idx);
Remove(0, 1, 0, k - 1, hor[idx][1], hor[idx][2], make_pair(hor[idx][0], idx));
} else {
break;
}
}
} else {
while (true) {
auto it = st_ver[x].lower_bound(make_pair(ll, -1));
if (it != st_ver[x].end() && it->first <= rr) {
int idx = it->second;
qv.push_back(idx);
Remove(1, 1, 0, k - 1, ver[idx][1], ver[idx][2], make_pair(ver[idx][0], idx));
} else {
break;
}
}
}
if (l == r) {
return;
}
int mid = l + r >> 1;
if (i <= mid) {
Query(t, x << 1, l, mid, i, ll, rr);
} else {
Query(t, x << 1 | 1, mid + 1, r, i, ll, rr);
}
};
for (int i = 0; i < sh; i++) {
if (dist[i] == -1) {
Insert(0, 1, 0, k - 1, hor[i][1], hor[i][2], make_pair(hor[i][0], i));
}
}
for (int i = 0; i < sv; i++) {
if (dist[sh + i] == -1) {
Insert(1, 1, 0, k - 1, ver[i][1], ver[i][2], make_pair(ver[i][0], i));
}
}
for (int q = 0; q < (int) que.size(); q++) {
int x = que[q];
if (x < sh) {
qv.clear();
Query(1, 1, 0, k - 1, hor[x][0], hor[x][1], hor[x][2]);
for (int i : qv) {
dist[sh + i] = dist[x] + 1;
que.push_back(sh + i);
}
} else {
x -= sh;
qv.clear();
Query(0, 1, 0, k - 1, ver[x][0], ver[x][1], ver[x][2]);
for (int i : qv) {
dist[i] = dist[x + sh] + 1;
que.push_back(i);
}
}
}
int res = inf;
for (int i = 0; i < sh; i++) {
if (hor[i][0] == v && hor[i][1] <= u && u <= hor[i][2]) {
res = min(res, dist[i]);
}
}
for (int i = 0; i < sv; i++) {
if (ver[i][0] == u && ver[i][1] <= v && v <= ver[i][2]) {
res = min(res, dist[i + sh]);
}
}
cout << res << '\n';
return 0;
}
Compilation message
golf.cpp: In lambda function:
golf.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid = l + r >> 1;
| ~~^~~
golf.cpp: In lambda function:
golf.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid = l + r >> 1;
| ~~^~~
golf.cpp: In lambda function:
golf.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
81 | int mid = l + r >> 1;
| ~~^~~
golf.cpp: In lambda function:
golf.cpp:394:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
394 | int mid = l + r >> 1;
| ~~^~~
golf.cpp: In lambda function:
golf.cpp:413:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
413 | int mid = l + r >> 1;
| ~~^~~
golf.cpp: In lambda function:
golf.cpp:450:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
450 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1672 KB |
Output is correct |
| 10 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 11 |
Correct |
10 ms |
1648 KB |
Output is correct |
| 12 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 13 |
Correct |
9 ms |
1628 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 15 |
Correct |
3 ms |
860 KB |
Output is correct |
| 16 |
Correct |
6 ms |
1372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1672 KB |
Output is correct |
| 10 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 11 |
Correct |
10 ms |
1648 KB |
Output is correct |
| 12 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 13 |
Correct |
9 ms |
1628 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 15 |
Correct |
3 ms |
860 KB |
Output is correct |
| 16 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 17 |
Correct |
13 ms |
3416 KB |
Output is correct |
| 18 |
Correct |
13 ms |
3672 KB |
Output is correct |
| 19 |
Correct |
13 ms |
3504 KB |
Output is correct |
| 20 |
Correct |
15 ms |
3420 KB |
Output is correct |
| 21 |
Correct |
14 ms |
3620 KB |
Output is correct |
| 22 |
Correct |
13 ms |
3420 KB |
Output is correct |
| 23 |
Correct |
13 ms |
3416 KB |
Output is correct |
| 24 |
Correct |
13 ms |
3420 KB |
Output is correct |
| 25 |
Correct |
13 ms |
3520 KB |
Output is correct |
| 26 |
Correct |
13 ms |
3552 KB |
Output is correct |
| 27 |
Correct |
3 ms |
860 KB |
Output is correct |
| 28 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 29 |
Correct |
6 ms |
1628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1880 KB |
Output is correct |
| 7 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 8 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 9 |
Correct |
9 ms |
1672 KB |
Output is correct |
| 10 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 11 |
Correct |
10 ms |
1648 KB |
Output is correct |
| 12 |
Correct |
9 ms |
1624 KB |
Output is correct |
| 13 |
Correct |
9 ms |
1628 KB |
Output is correct |
| 14 |
Correct |
10 ms |
1628 KB |
Output is correct |
| 15 |
Correct |
3 ms |
860 KB |
Output is correct |
| 16 |
Correct |
6 ms |
1372 KB |
Output is correct |
| 17 |
Correct |
13 ms |
3416 KB |
Output is correct |
| 18 |
Correct |
13 ms |
3672 KB |
Output is correct |
| 19 |
Correct |
13 ms |
3504 KB |
Output is correct |
| 20 |
Correct |
15 ms |
3420 KB |
Output is correct |
| 21 |
Correct |
14 ms |
3620 KB |
Output is correct |
| 22 |
Correct |
13 ms |
3420 KB |
Output is correct |
| 23 |
Correct |
13 ms |
3416 KB |
Output is correct |
| 24 |
Correct |
13 ms |
3420 KB |
Output is correct |
| 25 |
Correct |
13 ms |
3520 KB |
Output is correct |
| 26 |
Correct |
13 ms |
3552 KB |
Output is correct |
| 27 |
Correct |
3 ms |
860 KB |
Output is correct |
| 28 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 29 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 30 |
Correct |
3603 ms |
376232 KB |
Output is correct |
| 31 |
Correct |
3509 ms |
381212 KB |
Output is correct |
| 32 |
Correct |
3557 ms |
381592 KB |
Output is correct |
| 33 |
Correct |
3538 ms |
383008 KB |
Output is correct |
| 34 |
Correct |
3627 ms |
388244 KB |
Output is correct |
| 35 |
Correct |
3597 ms |
389336 KB |
Output is correct |
| 36 |
Correct |
3511 ms |
387016 KB |
Output is correct |
| 37 |
Correct |
3491 ms |
384452 KB |
Output is correct |
| 38 |
Correct |
3652 ms |
388536 KB |
Output is correct |
| 39 |
Correct |
3544 ms |
385540 KB |
Output is correct |
| 40 |
Correct |
609 ms |
192732 KB |
Output is correct |
| 41 |
Correct |
621 ms |
192752 KB |
Output is correct |
| 42 |
Correct |
615 ms |
194856 KB |
Output is correct |
| 43 |
Correct |
613 ms |
194772 KB |
Output is correct |
| 44 |
Correct |
614 ms |
196716 KB |
Output is correct |
| 45 |
Correct |
628 ms |
196540 KB |
Output is correct |
| 46 |
Correct |
628 ms |
196884 KB |
Output is correct |
| 47 |
Correct |
634 ms |
196956 KB |
Output is correct |
| 48 |
Correct |
617 ms |
196728 KB |
Output is correct |
| 49 |
Correct |
648 ms |
196628 KB |
Output is correct |
| 50 |
Correct |
6 ms |
1628 KB |
Output is correct |
| 51 |
Correct |
6 ms |
1592 KB |
Output is correct |
| 52 |
Correct |
6 ms |
1628 KB |
Output is correct |
