This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
//#define int long long
const int nmax = 1e6 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 17, tx = 26;
const ll mod = 998244353;
#define pii pair<int, int>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
struct node{
int x1, x2, y1, y2;
}a[nmax];
int n, rt, S, T, U, V;
vector<int> nen;
int gg(int u){
return lower_bound(nen.begin(), nen.end(), u) - nen.begin() + 1;
}
struct holder{
int x, l, r;
friend bool operator < (const holder &a, const holder&b){
if(a.x == b.x){
if(a.l == b.l) return a.r < b.r;
return a.l < b.l;
}
return a.x < b.x;
}
friend bool operator == (const holder &a, const holder&b){
return (a.x == b.x) && (a.l == b.l) &&(a.r == b.r);
}
};
vector<holder> A, B;
int tree[nmax << 2], lz[nmax << 2];
void build(int idx){
if(!idx) lz[1] = gg(-oo);
else lz[1] = gg(oo);
}
void fix(int id, int val){
if(!val) return;
tree[id] = val;
lz[id] = val;
}
void down(int id){
fix(id << 1, lz[id]);
fix(id << 1 | 1, lz[id]);
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val){
if(l > v || r < u || u > v) return;
if(l >= u && r <= v) return fix(id, val);
down(id);
int mid = r + l >> 1;
update(id << 1, l, mid, u, v,val);
update(id << 1 | 1, mid + 1, r, u, v, val);
}
#define update(l, r, val) update(1, 1, rt, l, r, val)
int get(int id, int l, int r, int u){
if(l == r) return tree[id];
down(id);
int mid = r + l >> 1;
if(u <= mid)return get(id << 1, l, mid, u);
return get(id << 1 | 1, mid + 1, r, u);
}
#define get(x) get(1, 1, rt, x)
int L[nmax], R[nmax];
void add(int x1, int y1, int x2, int y2){
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
A.push_back({y1, x1, x2});
A.push_back({y2, x1, x2});
B.push_back({x1, y1, y2});
B.push_back({x2, y1, y2});
}
struct hos{
int first, second, id;
friend bool operator < (const hos &a, const hos&b){
if(a.fi == b.fi){
if(a.se == b.se) return a.id < b.id;
return a.se < b.se;
}
return a.fi < b.fi;
}
friend bool operator == (const hos &a, const hos&b){
return (a.fi == b.fi) && (a.se == b.se) && (a.id == b.id);
}
};
vector<holder> one[2];
vector<int> adj[nmax];
//A doc
//B ngang
int ans[nmax][2];
vector<int> ola;
deque<pii> q;
struct clgt{
vector<int> tree;
void UPDATE(int id, int l, int r, int u, int val){
if(l > u || r < u) return;
if(l == r){
tree[id] = val;
return;
}
int mid = r + l >> 1;
UPDATE(id << 1, l, mid, u, val);
UPDATE(id << 1 | 1, mid + 1, r, u, val);
tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
void Find(int id, int l, int r, int u, int v, int k){
if(l > v || r < u || u > v || tree[id] < k) return;
if(l == r){
tree[id] = -1;
ola.push_back(l);
return;
}
int mid = r + l >> 1;
Find(id << 1, l, mid, u, v, k);
Find(id << 1 | 1, mid + 1, r, u, v, k);
tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
}
}FF[2][1 << 19];
vector<hos> st[2][1 << 19];
vector<pii> tr[2][1 << 19];
void BUILD(int id, int l, int r, int idx){
int lc = __lg(r - l + 1) + 2;
FF[idx][id].tree.resize(1 << lc);
if(l == r){
st[idx][id].push_back({one[idx][l].l, one[idx][l].r, l});
for(int i = 0; i < r - l + 1; ++i){
FF[idx][id].UPDATE(1, 0, r - l, i, st[idx][id][i].se);
}
return;
}
int mid = r + l >> 1;
BUILD(id << 1, l, mid, idx);
BUILD(id << 1 | 1, mid + 1, r, idx);
st[idx][id].resize(r - l + 1);
merge(st[idx][id << 1].begin(), st[idx][id << 1].end(), st[idx][id << 1 | 1].begin(), st[idx][id << 1 | 1].end(), st[idx][id].begin());
for(int i = 0; i < r - l + 1; ++i){
FF[idx][id].UPDATE(1, 0, r - l, i, st[idx][id][i].se);
}
}
vector<int> List;
void GET(int id, int l, int r, int u, int v, int k, int idx){
if(l > v || r < u || u > v) return;
if(l >= u && r <= v){
int le = 0, ri = st[idx][id].size() - 1, kq = st[idx][id].size();
while(le <= ri){
int mid = ri+ le >> 1;
if(st[idx][id][mid].fi > k){
kq = mid;
ri = mid - 1;
}
else le = mid + 1;
}
kq--;
FF[idx][id].Find(1, 0, r - l, 0, kq, k);
for(auto p : ola){
List.push_back(st[idx][id][p].id);
}
ola.clear();
return;
}
int mid = r + l >> 1;
GET(id << 1, l, mid, u, v, k, idx);
GET(id << 1 | 1, mid + 1, r, u, v, k, idx);
}
void solve(){
//tao canh
S = gg(S), T = gg(T);
U = gg(U), V = gg(V);
// cout << nen[U - 1]<< ' ' << nen[V - 1] << ' ';
add(gg(-oo), gg(-oo), gg(oo), gg(oo));
for(int i = 1; i <= n; ++i){
A.push_back({a[i].y1, a[i].x1 + 1, a[i].x2 - 1});
A.push_back({a[i].y2, a[i].x1 + 1, a[i].x2 - 1});
B.push_back({a[i].x1, a[i].y1 + 1, a[i].y2 - 1});
B.push_back({a[i].x2, a[i].y1 + 1, a[i].y2 - 1});
}
one[0].push_back({gg(-oo), gg(-oo), gg(oo)});
one[0].push_back({gg(oo), gg(-oo), gg(oo)});
one[1].push_back({gg(-oo), gg(-oo), gg(oo)});
one[1].push_back({gg(oo), gg(-oo), gg(oo)});
sort(A.begin(), A.end(), [](holder A, holder B){
return A.x < B.x;
});
vector<pii> tmp;
tmp.push_back({S, T});
tmp.push_back({U, V});
for(int i = 1; i <= n; ++i){
tmp.push_back({a[i].x1, a[i].y1});
tmp.push_back({a[i].x1, a[i].y2});
tmp.push_back({a[i].x2, a[i].y1});
tmp.push_back({a[i].x2, a[i].y2});
}
//#####
sort(tmp.begin(), tmp.end(), [](pii a, pii b){
return a.se < b.se;
});
build(0);
int pos = 0;
for(int i = 0; i < tmp.size(); ++i){
int x = tmp[i].fi, y = tmp[i].se;
while(pos < A.size() && A[pos].x < y){
update(A[pos].l, A[pos].r, A[pos].x);
++pos;
}
L[i] = get(x);
}
build(1);
pos = 0;
reverse(A.begin(), A.end());
for(int i = tmp.size() - 1; i >= 0; --i){
int x = tmp[i].fi, y = tmp[i].se;
while(pos < A.size() && A[pos].x > y){
update(A[pos].l, A[pos].r, A[pos].x);
++pos;
}
R[i] = get(x);
}
for(int i = 0; i < tmp.size(); ++i){
one[0].push_back({tmp[i].fi, L[i], R[i]});
}
//######
sort(B.begin(), B.end(), [](holder A, holder B){
return A.x < B.x;
});
sort(tmp.begin(), tmp.end(), [](pii a, pii b){
return a.fi < b.fi;
});
build(0); pos = 0;
for(int i = 0; i < tmp.size(); ++i){
int x = tmp[i].fi, y = tmp[i].se;
while(pos < B.size() && B[pos].x < x){
update(B[pos].l, B[pos].r, B[pos].x);
++pos;
}
L[i] = get(y);
}
build(1); pos = 0;
reverse(B.begin(), B.end());
for(int i = tmp.size() - 1; i >= 0; --i){
int x = tmp[i].fi, y = tmp[i].se;
while(pos < B.size() && B[pos].x > x){
update(B[pos].l, B[pos].r, B[pos].x);
++pos;
}
R[i] = get(y);
}
for(int i = 0; i < tmp.size(); ++i){
one[1].push_back({tmp[i].se, L[i], R[i]});
}
sort(one[0].begin(), one[0].end());
one[0].erase(unique(one[0].begin(), one[0].end()), one[0].end());
sort(one[1].begin(), one[1].end());
one[1].erase(unique(one[1].begin(), one[1].end()), one[1].end());
//#####
memset(ans, 0x3f, sizeof ans);
for(int idx = 0; idx < 2; ++idx) BUILD(1, 0, one[idx].size() - 1, idx);
for(int i = 0; i < one[0].size(); ++i){
if(S == one[0][i].x && one[0][i].l <= T && one[0][i].r >= T ){
q.push_back({i, 0});
ans[i][0] = 1;
}
}
for(int i = 0; i < one[1].size(); ++i){
if(T == one[1][i].x && one[1][i].l <= S && one[1][i].r >= S){
q.push_back({i, 1});
ans[i][1] = 1;
}
}
while(q.size()){
pii tmp = q.front(); q.pop_front();
if(tmp.se == 0){
int x = one[0][tmp.fi].x, l = one[0][tmp.fi].l, r = one[0][tmp.fi].r;
int le = 0, ri = one[1].size() - 1, Lef = one[1].size(), Righ =-1;
while(le <= ri){
int mid = ri + le >> 1;
if(one[1][mid].x >= l){
Lef = mid;
ri = mid - 1;
}
else le = mid + 1;
}
le = 0, ri = one[1].size() - 1;
while(le <= ri){
int mid = ri + le >> 1;
if(one[1][mid].x <= r){
Righ = mid;
le = mid + 1;
}
else ri = mid - 1;
}
GET(1, 0, one[1].size(), Lef, Righ, x, 1);
for(auto j : List){
int y = one[1][j].x, le = one[1][j].l, ri = one[1][j].r;
if(le <= x && x <= ri && l <= y && y <= r){
// if(V == y && le <= U && ri >= U){
// cout << ans[tmp.fi][0] + 1;
// exit(0);
// }
if(ans[j][1] > oo){
ans[j][1] = ans[tmp.fi][0] + 1;
q.push_back({j, 1});
}
}
}
List.clear();
}
else{
int x = one[1][tmp.fi].x, l = one[1][tmp.fi].l, r = one[1][tmp.fi].r;
int le = 0, ri = one[0].size() - 1, Lef = one[0].size(), Righ =-1;
while(le <= ri){
int mid = ri + le >> 1;
if(one[0][mid].x >= l){
Lef = mid;
ri = mid - 1;
}
else le = mid + 1;
}
le = 0, ri = one[0].size() - 1;
while(le <= ri){
int mid = ri + le >> 1;
if(one[0][mid].x <= r){
Righ = mid;
le = mid + 1;
}
else ri = mid - 1;
}
// cout << Lef << ' ' << Righ << endl;
GET(1, 0, one[0].size(), Lef, Righ, x, 0);
for(auto j : List){
int y = one[0][j].x, le = one[0][j].l, ri = one[0][j].r;
// cout << nen[y - 1] << ' ' << nen[le - 1] << ' ' << nen[ri- 1] << endl;
if(le <= x && x <= ri && l <= y && y <= r){
// if(U == y && le <= V && ri >= V){
// cout << ans[tmp.fi][1] + 1;
// exit(0);
// }
if(ans[j][0] > oo){
ans[j][0] = ans[tmp.fi][1] + 1;
q.push_back({j, 0});
}
}
}
// exit(0);
List.clear();
}
}
int mi = oo;
for(int i = 0; i < one[0].size(); ++i){
if(U == one[0][i].x && one[0][i].l <= V && one[0][i].r >= V ){
mi = min(ans[i][0], mi);
}
// cout << nen[one[0][i].x - 1]<< ' ' << nen[one[0][i].l - 1] << ' ' << nen[one[0][i].r - 1] << ' ' << ans[i][0] << endl;
}
for(int i = 0; i < one[1].size(); ++i){
if(V == one[1][i].x && one[1][i].l <= U && one[1][i].r >= U){
mi = min(mi, ans[i][1]);
}
// cout << nen[one[1][i].x - 1] << ' ' << nen[one[1][i].l - 1] << ' ' << nen[one[1][i].r - 1] << ' ' << ans[i][1] << endl;
}
cout << mi;
}
int vis[200][200];
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> S >> T >> U >> V >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i].x1 >> a[i].x2 >> a[i].y1 >> a[i].y2;
nen.push_back(a[i].x1);
nen.push_back(a[i].x2);
nen.push_back(a[i].y1);
nen.push_back(a[i].y2);
nen.push_back(a[i].x1 - 1);
nen.push_back(a[i].x2 + 1);
nen.push_back(a[i].y1 - 1);
nen.push_back(a[i].y2 + 1);
}
// for(int i = 1; i <= n; ++i){
// for(int x = a[i].x1; x <= a[i].x2; ++x){
// for(int y= a[i].y1; y <= a[i].y2;++y)vis[x][y] = i;
// }
// }
// vis[S][T] = vis[U][V]= 9;
// for(int i = 0; i <= 30; ++i){
// for(int j = 0; j <= 30; ++j){
//// if(vis[i][j] == 1) cout << "#";
//// else if(vis[i][j] == 2) cout << "?";
//// else cout << ".";
// cout << vis[i][j];
// }
// cout << endl;
// }
for(int x = -1; x <= 1; ++x){
nen.push_back(S + x); nen.push_back(U + x);
nen.push_back(T + x); nen.push_back(V + x);
nen.push_back(-oo + x); nen.push_back(oo + x);
}
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
rt = nen.size();
for(int i = 1; i <= n; ++i){
a[i].x1 = gg(a[i].x1);
a[i].x2 = gg(a[i].x2);
a[i].y1 = gg(a[i].y1);
a[i].y2 = gg(a[i].y2);
}
//tao canh
solve();
}
/*
-1000000005 -1000000005 1000000005
1 -1000000005 1000000005
6 -1000000005 1000000005
1000000005 -1000000005 1000000005
4 -1000000005 1000000005
9 4 23 9
5
12 27 14 30
8 19 8 9
6 21 5 7
1 4 4 29
11 20 11 12
*/
Compilation message (stderr)
golf.cpp: In function 'void update(int, int, int, int, int, int)':
golf.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = r + l >> 1;
| ~~^~~
golf.cpp: In function 'int get(int, int, int, int)':
golf.cpp:70:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid = r + l >> 1;
| ~~^~~
golf.cpp: In member function 'void clgt::UPDATE(int, int, int, int, int)':
golf.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid = r + l >> 1;
| ~~^~~
golf.cpp: In member function 'void clgt::Find(int, int, int, int, int, int)':
golf.cpp:126:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
126 | int mid = r + l >> 1;
| ~~^~~
golf.cpp: In function 'void BUILD(int, int, int, int)':
golf.cpp:146:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
146 | int mid = r + l >> 1;
| ~~^~~
golf.cpp: In function 'void GET(int, int, int, int, int, int, int)':
golf.cpp:162:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
162 | int mid = ri+ le >> 1;
| ~~^~~~
golf.cpp:178:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
178 | int mid = r + l >> 1;
| ~~^~~
golf.cpp: In function 'void solve()':
golf.cpp:216:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
216 | for(int i = 0; i < tmp.size(); ++i){
| ~~^~~~~~~~~~~~
golf.cpp:218:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | while(pos < A.size() && A[pos].x < y){
| ~~~~^~~~~~~~~~
golf.cpp:229:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
229 | while(pos < A.size() && A[pos].x > y){
| ~~~~^~~~~~~~~~
golf.cpp:235:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
235 | for(int i = 0; i < tmp.size(); ++i){
| ~~^~~~~~~~~~~~
golf.cpp:247:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | for(int i = 0; i < tmp.size(); ++i){
| ~~^~~~~~~~~~~~
golf.cpp:249:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | while(pos < B.size() && B[pos].x < x){
| ~~~~^~~~~~~~~~
golf.cpp:259:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
259 | while(pos < B.size() && B[pos].x > x){
| ~~~~^~~~~~~~~~
golf.cpp:265:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
265 | for(int i = 0; i < tmp.size(); ++i){
| ~~^~~~~~~~~~~~
golf.cpp:275:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
275 | for(int i = 0; i < one[0].size(); ++i){
| ~~^~~~~~~~~~~~~~~
golf.cpp:282:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
282 | for(int i = 0; i < one[1].size(); ++i){
| ~~^~~~~~~~~~~~~~~
golf.cpp:294:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
294 | int mid = ri + le >> 1;
| ~~~^~~~
golf.cpp:303:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
303 | int mid = ri + le >> 1;
| ~~~^~~~
golf.cpp:330:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
330 | int mid = ri + le >> 1;
| ~~~^~~~
golf.cpp:339:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
339 | int mid = ri + le >> 1;
| ~~~^~~~
golf.cpp:368:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
368 | for(int i = 0; i < one[0].size(); ++i){
| ~~^~~~~~~~~~~~~~~
golf.cpp:375:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<holder>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
375 | for(int i = 0; i < one[1].size(); ++i){
| ~~^~~~~~~~~~~~~~~
golf.cpp: At global scope:
golf.cpp:385:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
385 | main(){
| ^~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
