#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];
});
int ptr = 0;
vector<int> from(n);
vector<int> to(n);
for (int i : order) {
while (ptr < n && d[order[ptr]] < b[i]) {
Modify(1, 0, k - 1, a[order[ptr]] + 1, c[order[ptr]] - 1, d[order[ptr]]);
ptr += 1;
}
from[i] = QueryMax(1, 0, k - 1, a[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];
});
ptr = 0;
for (int i : order) {
while (ptr < n && b[order[ptr]] > d[i]) {
Modify(1, 0, k - 1, a[order[ptr]] + 1, c[order[ptr]] - 1, b[order[ptr]]);
}
to[i] = QueryMin(1, 0, k - 1, a[i]);
}
for (int i = 0; i < n; i++) {
ver.push_back({a[i], from[i], to[i]});
}
}
for (int i = 0; i < n; i++) {
{
// left
/* int from = 0;
for (int j = 0; j < n; j++) {
if (d[j] < b[i] && a[j] < a[i] && a[i] < c[j]) {
from = max(from, d[j]);
}
}
int to = k - 1;
for (int j = 0; j < n; j++) {
if (b[j] > d[i] && a[j] < a[i] && a[i] < c[j]) {
to = min(to, b[j]);
}
}
ver.push_back({a[i], from, to}); */
}
{
// right
int from = 0;
for (int j = 0; j < n; j++) {
if (d[j] < b[i] && a[j] < c[i] && c[i] < c[j]) {
from = max(from, d[j]);
}
}
int to = k - 1;
for (int j = 0; j < n; j++) {
if (b[j] > d[i] && a[j] < c[i] && c[i] < c[j]) {
to = min(to, b[j]);
}
}
ver.push_back({c[i], from, to});
}
{
// bottom
int from = 0;
for (int j = 0; j < n; j++) {
if (c[j] < a[i] && b[j] < b[i] && b[i] < d[j]) {
from = max(from, c[j]);
}
}
int to = k - 1;
for (int j = 0; j < n; j++) {
if (a[j] > c[i] && b[j] < b[i] && b[i] < d[j]) {
to = min(to, a[j]);
}
}
hor.push_back({b[i], from, to});
}
{
// top
int from = 0;
for (int j = 0; j < n; j++) {
if (c[j] < a[i] && b[j] < d[i] && d[i] < d[j]) {
from = max(from, c[j]);
}
}
int to = k - 1;
for (int j = 0; j < n; j++) {
if (a[j] > c[i] && b[j] < d[i] && d[i] < d[j]) {
to = min(to, a[j]);
}
}
hor.push_back({d[i], from, to});
}
}
{
// 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:295:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
295 | int mid = l + r >> 1;
| ~~^~~
golf.cpp: In lambda function:
golf.cpp:314:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
314 | int mid = l + r >> 1;
| ~~^~~
golf.cpp: In lambda function:
golf.cpp:351:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
351 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10022 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10022 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
10022 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
