Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- .:*+=%@@@@@@=-.
- .:=@#@@@#@@#######%==*.
- .-=####@######%*-.....:%##%.
- .*@###########%+:--........-%@-
- .*@##############@+--.........-:%-
- .+##################@==%%%%=+*:----+.
- .-@####################%++%@@@@@=+**%@@*
- .%###################@%%@@@###@%+:--%@@%.
- -@###################@%%%%*::*%++:-----=@+.
- -#####################@%=++++++*:-------.-=:
- .+####################@%++*::-:::--::*:::***=:
- .@#####################%=++*::::-:::++*=##@@#@-
- ..#####################@%%=++**:::::**+%@#@%%##-..
- .%####################@@%=+++*+****::*=@######@.
- .=######################@%%==+==++**+=@%@##@###+:...
- -#######################@@@%%%===++=@@@%=++===*::--...
- -########################@@@@@@@%==%%=++==@@:::::*:--.
- ..:#########################@@@@@@%%======++++::-..:-.--...
- %#############################@###@%%@@%==%=%*----.--.::---.
- #############################################*-:*:-:---*---- .
- #############################################*--*--:---*---:-.
- #############################################+--::--::-*::-::.
- ###########################################+:*-.---.---.:---*-..
- ###########################################**:-----------------.
- ##########################################@::**:--::::::--:::::-
- ###########################################:--:*:::::::::**::*+*
- ###########################################=:::***::::::**:::*+*
- ############################@@@@@@#########@+****::::********+++
- ############################@%%%%%@@@@@@@###%+***::::::::***+==+
- ############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
- #############################@%%%%%%%%%%@#####=::--------:*=%@%+
- %###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
- ----------------------------------------------
- --------------------------------------------
- ----------------------------------------------
- --------------------------------------------
- ----------------------------------------------
- o###########oo
- o##" ""##o
- o#" "##
- o#" "#o
- #" ## ## "##
- #" ##
- # ################### #
- # #
- # #
- # #
- # #
- # #
- # #
- #o #
- "#o ##
- "#o ##
- "#o o#"
- "#o ##
- "#o o#"
- "#ooo ooo#######oo
- ############### "######o
- o###"" "###o # ###
- o###o oooo ### oo####"
- o###**# #**# ############"
- ""##""""""""""########### #
- # oooooooo#"#** ## #
- # # # # ** ## #
- #o# #o# *****###ooo#
- ##
- ## o###o
- ## o##***##
- o########## #***#**##o
- o##" ""### #***##***#
- o#######o ### oo#### ##**####*#
- o##" ""#############"" ##****###
- ##" ## ##*##*###
- ## ### ##### ##
- ## ### # ## #
- ## ## #
- ## ##
- ## ###
- ## ###oo
- ### ""###
- ###
- ###
- */
- ///YEAH IM THE BEST I'VE EVER WAS
- ///SO HAPPY
- #include <bits/stdc++.h>
- #define fr first
- #define sc second
- #define m_p make_pair
- //#include <ext/pb_ds/assoc_container.hpp>
- //using namespace __gnu_pbds;
- //gp_hash_table<int, int> table;
- //#pragma GCC optimize("O3")
- //#pragma GCC optimize("Ofast,no-stack-protector")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
- //#pragma GCC target("avx,tune=native")
- //float __attribute__((aligned(32)))
- /*char memory[(int)1e8];
- char memorypos;
- inline void * operator new(size_t n){
- char * ret = memory + memorypos;
- memorypos += n;
- return (void *)ret;
- }
- inline void operator delete(void *){}
- */
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef unsigned int uint;
- ll sqr(ll x){
- return x * x;
- }
- int mysqrt(ll x){
- int l = 0, r = 1e9 + 1;
- while (r - l > 1){
- int m = (l + r) / 2;
- if (m * (ll)m <= x)
- l = m;
- else
- r = m;
- }
- return l;
- }
- mt19937 rnd(1227);
- mt19937_64 rndll(12365);
- ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;
- ll myrand(){
- ll ZR = (XR * AR + YR * BR + CR) % MODR;
- XR = YR;
- YR = ZR;
- return ZR;
- }
- int gcd(int a, int b){
- return a ? gcd(b % a, a) : b;
- }
- int gcdex(int a, int b, int &x, int &y){
- if (a == 0){
- x = 0;
- y = 1;
- return b;
- }
- int x1, y1;
- int ret = gcdex(b % a, a, x1, y1);
- x = y1 - (b / a) * x1;
- y = x1;
- return ret;
- }
- const int Mod = 1e9 + 7;
- int Bpow(int x, int y){
- int ret = 1;
- int w = x;
- while (y){
- if (y & 1)
- ret = (ret * (ll)w) % Mod;
- w = (w * (ll)w) % Mod;
- y >>= 1;
- }
- return ret;
- }
- int Bdiv(int x){
- int a, b;
- gcdex(x, Mod, a, b);
- if (a < 0)
- a += Mod;
- return a;
- }
- int Bdiv(int x, int y){
- return (x * (ll)Bpow(y, Mod - 2)) % Mod;
- }
- void setmin(int &x, int y){
- x = min(x, y);
- }
- void setmax(int &x, int y){
- x = max(x, y);
- }
- void setmin(ll &x, ll y){
- x = min(x, y);
- }
- void setmax(ll &x, ll y){
- x = max(x, y);
- }
- const ll llinf = 2e18 + 100;
- const double eps = 1e-9;
- const int maxn = 4e5 + 100, maxw = 1e6 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17;
- struct seg_tree{
- bool v;
- int l, r;
- };
- seg_tree p[maxn * 100];
- int cnt;
- int create(){
- return cnt++;
- }
- int build(int l, int r){
- int t = create();
- if (l == r)
- return t;
- int m = (l + r) / 2;
- p[t].l = build(l, m);
- p[t].r = build(m + 1, r);
- return t;
- }
- int update(int now, int l, int r, int id, int w){
- int t = create();
- if (l == r){
- p[t].v = w;
- return t;
- }
- int m = (l + r) / 2;
- if (id <= m)
- p[t].l = update(p[now].l, l, m, id, w),
- p[t].r = p[now].r;
- else
- p[t].l = p[now].l,
- p[t].r = update(p[now].r, m + 1, r, id, w);
- p[t].v = p[p[t].l].v | p[p[t].r].v;
- return t;
- }
- void get(int t, int tl, int tr, int l, int r, vector<int> &h){
- if (l > r || !p[t].v)
- return;
- if (tl == tr){
- h.push_back(l);
- p[t].v = 0;
- return;
- }
- int m = (tl + tr) / 2;
- get(p[t].l, tl, m, l, min(r, m), h);
- get(p[t].r, m + 1, tr, max(l, m + 1), r, h);
- p[t].v = p[p[t].l].v | p[p[t].r].v;
- }
- pair<int, int> start, finish;
- int n;
- pair<pair<int, int>, pair<int, int> > rec[maxn];
- map<int, int> mpik;
- vector<int> srt;
- vector<pair<int, pair<int, int> > > seg[2];
- int d[maxn];
- int q[maxn];
- pair<int, int> bo[maxn];
- int main()
- {
- #ifdef ONPC
- //ifstream cin("a.in");
- //ofstream cout("a.out");
- freopen("a.in", "r", stdin);
- freopen("a.out", "w", stdout);
- #else
- //ifstream cin("gymnasts.in");
- //ofstream cout("gymnasts.out");
- //freopen("sort.in", "r", stdin);
- //freopen("sort.out", "w", stdout);
- #endif // ONPC
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- vector<pair<int, pair<int, int> > > o;
- cin >> start.fr >> start.sc >> finish.fr >> finish.sc;
- cin >> n;
- for (int i = 0; i < n; i++)
- cin >> rec[i].fr.fr >> rec[i].fr.sc >> rec[i].sc.fr >> rec[i].sc.sc;
- for (int t = 0; t < 2; t++){
- for (int i = 0; i < n; i++)
- srt.push_back(rec[i].fr.fr),
- srt.push_back(rec[i].fr.sc);
- srt.push_back(start.fr);
- srt.push_back(finish.fr);
- sort(srt.begin(), srt.end());
- srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
- for (int i : srt)
- mpik[i] = mpik.size() - 1;
- for (int i = 0; i < n; i++)
- rec[i].fr.fr = mpik[rec[i].fr.fr],
- rec[i].fr.sc = mpik[rec[i].fr.sc];
- start.fr = mpik[start.fr];
- finish.fr = mpik[finish.fr];
- srt.clear();
- mpik.clear();
- for (int i = 0; i < n; i++)
- swap(rec[i].fr, rec[i].sc);
- swap(start.fr, start.sc);
- swap(finish.fr, finish.sc);
- }
- for (int t = 0; t < 2; t++){
- vector<pair<int, pair<int, int> > > que;
- for (int i = 0; i < n; i++)
- que.push_back(m_p(rec[i].sc.fr, rec[i].fr)),
- que.push_back(m_p(rec[i].sc.sc, rec[i].fr)),
- que.push_back(m_p(rec[i].sc.fr, m_p(inf, rec[i].fr.fr))),
- que.push_back(m_p(rec[i].sc.fr, m_p(inf, rec[i].fr.sc))),
- que.push_back(m_p(rec[i].sc.sc, m_p(-inf, rec[i].fr.fr))),
- que.push_back(m_p(rec[i].sc.sc, m_p(-inf, rec[i].fr.sc))),
- swap(rec[i].fr, rec[i].sc);
- que.push_back(m_p(start.sc, m_p(start.fr, start.fr)));
- que.push_back(m_p(finish.sc, m_p(finish.fr, finish.fr)));
- swap(start.fr, start.sc);
- swap(finish.fr, finish.sc);
- sort(que.begin(), que.end());
- set<int> st;
- st.insert(-1);
- st.insert(inf);
- for (auto its : que)
- if (its.sc.fr == -inf)
- st.erase(its.sc.sc);
- else
- if (its.sc.fr == inf)
- st.insert(its.sc.sc);
- else{
- set<int> :: iterator it = st.upper_bound(its.sc.fr);
- it--;
- int le = *it;
- it = st.lower_bound(its.sc.sc);
- seg[t].push_back(m_p(its.fr, m_p(le, *it)));
- }
- sort(seg[t].begin(), seg[t].end());
- seg[t].resize(unique(seg[t].begin(), seg[t].end()) - seg[t].begin());
- }
- n = seg[0].size() + seg[1].size();
- for (int t = 0; t < 2; t++){
- for (int i = 0; i < seg[t].size(); i++){
- int l = lower_bound(seg[!t].begin(), seg[!t].end(), m_p(seg[t][i].sc.fr, m_p(-inf, -inf))) - seg[!t].begin();
- int r = upper_bound(seg[!t].begin(), seg[!t].end(), m_p(seg[t][i].sc.sc, m_p(inf, inf))) - seg[!t].begin() - 1;
- if (!t)
- l += seg[0].size(), r += seg[0].size();
- bo[i + t * seg[0].size()] = m_p(l, r);
- }
- vector<pair<int, pair<int, int> > > que;
- for (int i = 0; i < seg[t].size(); i++)
- que.push_back(m_p(seg[t][i].fr, m_p(i + t * seg[0].size(), 0)));
- for (int i = 0; i < seg[!t].size(); i++)
- que.push_back(m_p(seg[!t][i].sc.fr, m_p(-inf, i + !t * seg[0].size()))),
- que.push_back(m_p(seg[!t][i].sc.sc, m_p(inf, i + !t * seg[0].size())));
- sort(que.begin(), que.end());
- int now = build(0, n - 1);
- for (auto its : que)
- if (its.sc.fr == -inf)
- now = update(now, 0, n - 1, its.sc.sc, 1);
- else
- if (its.sc.fr == inf)
- now = update(now, 0, n - 1, its.sc.sc, 0);
- else
- q[its.sc.fr] = now;
- }
- for (int i = 0; i < n; i++)
- d[i] = -1;
- int sta, stb, fina, finb;
- for (int i = 0; i < seg[0].size(); i++)
- if (seg[0][i].fr == start.sc && seg[0][i].sc.fr <= start.fr && seg[0][i].sc.sc >= start.fr)
- sta = i;
- for (int i = 0; i < seg[1].size(); i++)
- if (seg[1][i].fr == start.fr && seg[1][i].sc.fr <= start.sc && seg[1][i].sc.sc >= start.sc)
- stb = seg[0].size() + i;
- for (int i = 0; i < seg[0].size(); i++)
- if (seg[0][i].fr == finish.sc && seg[0][i].sc.fr <= finish.fr && seg[0][i].sc.sc >= finish.fr)
- fina = i;
- for (int i = 0; i < seg[1].size(); i++)
- if (seg[1][i].fr == finish.fr && seg[1][i].sc.fr <= finish.sc && seg[1][i].sc.sc >= finish.sc)
- finb = seg[0].size() + i;
- d[sta] = 0;
- d[stb] = 0;
- queue<int> que;
- que.push(sta);
- que.push(stb);
- while (!que.empty()){
- int id = que.front();
- que.pop();
- if (id == fina || id == finb){
- cout << d[id] + 1;
- return 0;
- }
- vector<int> g;
- get(q[id], 0, n - 1, bo[id].fr, bo[id].sc, g);
- for (int i : g)
- if (d[i] == -1)
- d[i] = d[id] + 1, que.push(i);
- }
- assert(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement