제출 #122463

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122463		egorlifar	Golf (JOI17_golf)	C++17	0 / 100	80 ms	55416 KiB

golf

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <chrono>
 
using namespace std;

template<class T1, class T2> inline int chkmin(T1 &x, const T2 &y) {
    if (x > y) {
        x = y;
        return 1;
    }
    else {
        return 0;
    }
}

template<class T1, class T2> inline int chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
        return 1;
    }
    else {
        return 0;
    }
}

#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define mp make_pair
#define pb push_back
#define read(FILENAME) freopen((string(FILENAME) + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((string(FILENAME) + ".out").c_str(), "w", stdout);

template<class iterator> void output(iterator begin, iterator end, ostream &out = cerr) {
    while (begin != end) {
        out << (*begin) << " ";
        begin++;
    }
    out << endl;
}


template<class T> void output(const T &x, ostream &out = cerr) {
    output(x.begin(), x.end(), out);
}

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
}
const int MAXN = 100228;


int s, t, u, v;
int n;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
vector<int> vx;
vector<int> vy;


int getx(int x) {
    return lower_bound(all(vx), x) - vx.begin();
}


int gety(int y) {
    return lower_bound(all(vy), y) - vy.begin();
}



struct rmq
{
    vector<int> d, mod;
    int ss = 1;
    void init(int n) {
        ss = 1;
        while (ss < n) {
            ss <<= 1;
        }
        d.resize(2 * ss);
        mod.resize(2 * ss);
        for (auto &x: d) {
            x = -1;
        }
        for (auto &x: mod) {
            x = -1;
        }
    }
    void push(int v) {
        if (mod[v] != -1) {
            d[v] = mod[v];
            if (v < ss) {
                mod[v * 2] = mod[v];
                mod[v * 2 + 1] = mod[v];
            }
            mod[v] = -1;
        }
    }
    void add(int v, int vl, int vr, int l, int r, int x) {
        if (vl > r || vr < l || l > r) {
            return;
        }
        if (l <= vl && vr <= r) {
            mod[v] = x;
            return;
        }
        push(v);
        add(v * 2, vl, (vl + vr) / 2, l, r, x);
        add(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x);
    }
    int getval(int v, int vl, int vr, int i) {
        push(v);
        if (vl == vr) {
            return d[v];
        }
        int mid = (vl + vr) / 2;
        if (i <= mid) {
            return getval(v * 2, vl, mid, i);
        }   
        return getval(v * 2 + 1, mid + 1, vr, i);
    }
};


rmq kek;

vector<int> z[MAXN * 2], z1[MAXN * 2];
vector<int> q[MAXN * 2], q1[MAXN * 2], zs[MAXN * 2], zs1[MAXN * 2];
int last[MAXN * 2], last1[MAXN * 2];
map<pair<int, int>, int> who;
vector<pair<int, int> > g[MAXN * 10];
int dist[MAXN * 10][5];


void add(int x, int y, int x1, int y1, int t) {
    g[who[{x, y}]].pb({who[{x1, y1}], t});
   // g[who[{x1, y1}]].pb({who[{x, y}], t ^ 1});
    //cout << x << ' ' << y << ' ' << x1 << ' ' << y1 << endl;
}


int main() {
    fast_io();
    //read("input");
    cin >> s >> t >> u >> v;
    cin >> n;
    vx.pb(s);
    vx.pb(u);
    vy.pb(t);
    vy.pb(v);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        vx.pb(a[i]);
        vx.pb(b[i]);
        vy.pb(c[i]);
        vy.pb(d[i]);
    }
    sort(all(vx));
    vx.resize(distance(vx.begin(), unique(all(vx))));
    sort(all(vy));
    vy.resize(distance(vy.begin(), unique(all(vy))));
    s = getx(s);
    u = getx(u);
    t = gety(t);
    v = gety(v);
   // cout << s << ' ' << t << ' ' << u << ' ' << v << endl;
    for (int i = 0; i < n; i++) {
        a[i] = getx(a[i]);
        b[i] = getx(b[i]);
        c[i] = gety(c[i]);
        d[i] = gety(d[i]);
        q[a[i]].pb(i);
        z[b[i]].pb(i);
        q1[c[i]].pb(i);
        z1[d[i]].pb(i);
       // cout << a[i] << ' ' << b[i] << ' ' << c[i] << ' ' << d[i] << endl;
    }
    set<pair<int, int> > st;
    for (int i = 0; i < n; i++) {
        st.insert({a[i], c[i]});
        st.insert({a[i], d[i]});
        st.insert({b[i], c[i]});
        st.insert({b[i], d[i]});
    }
    st.insert({s, t});
    st.insert({u, v});
    for (int i = 0; i < sz(vy); i++) {
        st.insert({s, i});
         st.insert({u, i});
    }
    for (int i = 0; i < sz(vx); i++) {
        st.insert({i, t});
         st.insert({i, v});
    }
    kek.init(sz(vy));
    for (int i = 0; i < max(sz(vx), sz(vy)); i++) {
        last[i] = -1;
        last1[i] = -1;
    }   
    for (int i = 0; i < sz(vx); i++) {
        for (auto x: z[i]) {
            //cout << i << endl;
            kek.add(1, 1, kek.ss, c[x] + 1, d[x] + 1, i);
        }
        if (i == s) {
            int f = kek.getval(1, 1, kek.ss, t + 1);
           // cout << f << ' ' << t << endl;
            st.insert({f, t});
        }
        if (i == u) {
            int f = kek.getval(1, 1, kek.ss, t + 1);
            st.insert({f, v});
        }
        for (auto y: q[i]) {
            int f = kek.getval(1, 1, kek.ss, c[y] + 1);
            st.insert({f, c[y]});
            f = kek.getval(1, 1, kek.ss, d[y] + 1);
            st.insert({f, d[y]});
        }
    }
    kek.init(sz(vy));
    for (int i = sz(vx) - 1; i >= 0; i--) {
        for (auto x: q[i]) {
           // cout << i << endl;
            kek.add(1, 1, kek.ss, c[x] + 1, d[x] + 1, i);
        }
         if (i == s) {
            int f = kek.getval(1, 1, kek.ss, t + 1);
         //   cout << f << ' ' << t << endl;
          //  cout << f << ' ' << t << endl;
            st.insert({f, t});
        }
        if (i == u) {
            int f = kek.getval(1, 1, kek.ss, v + 1);
            st.insert({f, v});
        }
        for (auto y: z[i]) {
            int f = kek.getval(1, 1, kek.ss, c[y] + 1);
            st.insert({f, c[y]});
            f = kek.getval(1, 1, kek.ss, d[y] + 1);
            st.insert({f, d[y]});
        }
    }
     kek.init(sz(vx));
    for (int i = 0; i < sz(vy); i++) {
        for (auto x: z1[i]) {
            kek.add(1, 1, kek.ss, a[x] + 1, b[x] + 1, i);
        }
        if (i == t) {
            int f = kek.getval(1, 1, kek.ss, s + 1);
            st.insert({s, f});
        }
        if (i == v) {
            int f = kek.getval(1, 1, kek.ss, u + 1);
            st.insert({u, f});
        }
        for (auto y: q1[i]) {
            int f = kek.getval(1, 1, kek.ss, a[y] + 1);
            st.insert({a[y], f});
            f = kek.getval(1, 1, kek.ss, b[y] + 1);
            st.insert({b[y], f});
        }
    }
    kek.init(sz(vx));
    for (int i = sz(vy) - 1; i >= 0; i--) {
        for (auto x: q1[i]) {
            kek.add(1, 1, kek.ss, a[x] + 1, b[x] + 1, i);
        }
        if (i == t) {
            int f = kek.getval(1, 1, kek.ss, s + 1);
            st.insert({s, f});
        }
        if (i == v) {
            int f = kek.getval(1, 1, kek.ss, u + 1);
            st.insert({u, f});
        }
        for (auto y: z1[i]) {
            int f = kek.getval(1, 1, kek.ss, a[y] + 1);
            st.insert({a[y], f});
            f = kek.getval(1, 1, kek.ss, b[y] + 1);
            st.insert({b[y], f});
        }
    }

    vector<pair<int, int> > st1;
    for (auto x: st) {
        if (x.first < 0 || x.second < 0) {
            continue;
        }
        st1.pb(x);
    }
    int it = 0;
    for (auto x: st1) {
        who[x] = it;
        //cout << x.first << ' ' << x.second << endl;
        it++;
        zs[x.first].pb(x.second);
        zs1[x.second].pb(x.first);
    }
     kek.init(sz(vy));
    for (int i = 0; i < sz(vx); i++) {
         for (auto x: z[i]) {
            //cout << i << endl;
            kek.add(1, 1, kek.ss, c[x] + 2, d[x], i);
        }
        for (auto y: zs[i]) {
            if (last[y] != -1) {
                int ft = kek.getval(1, 1, kek.ss, y + 1);
                // cout << last[y] << ' ' << y << ' ' << i << ' ' << y << endl;
                if (ft == -1 || ft <= last[y]) {
                    add(last[y], y, i, y, 0);
                }
            }
            last[y] = i;
        }
       
    }
     kek.init(sz(vx));
     for (int i = 0; i < sz(vy); i++) {
         for (auto x: z1[i]) {
            kek.add(1, 1, kek.ss, a[x] + 2, b[x], i);
        }
        for (auto y: zs1[i]) {
            if (last1[y] != -1) {
                //cout << y << ' ' << last1[y] << ' ' << y << ' ' << i << endl;
                 int ft = kek.getval(1, 1, kek.ss, y + 1);
                //cout << ft << endl;
                if (ft == -1 || ft <= last1[y]) {
                add(y, last1[y], y, i,  2);
            }
            }
            last1[y] = i;
        }
       
    }
    for (int i = 0; i < max(sz(vx), sz(vy)); i++) {
        last[i] = -1;
        last1[i] = -1;
    }   
    kek.init(sz(vy));
    for (int i = sz(vx) - 1; i >= 0; i--) {
       for (auto x: q[i]) {
            kek.add(1, 1, kek.ss, c[x] + 2, d[x], i);
        }
        for (auto y: zs[i]) {
            if (last[y] != -1) {
                int ft = kek.getval(1, 1, kek.ss, y + 1);
                if (ft == -1 || ft >= last[y]) {
                add(last[y], y, i, y, 1);
            }
            }
            last[y] = i;
        }
         
    }
     kek.init(sz(vx));
     for (int i = sz(vy) - 1; i >= 0; i--) {
        for (auto x: q1[i]) {
            kek.add(1, 1, kek.ss, a[x] + 2, b[x], i);
        }
        for (auto y: zs1[i]) {
            if (last1[y] != -1) {
                int ft = kek.getval(1, 1, kek.ss, y + 1);
                if (ft == -1 || ft >= last1[y]) {
                add(y, last1[y], y, i, 3);
            }
            }
            last1[y] = i;
        }
    }
    int m = sz(st1);
    int start = who[{s, t}];
    int finish = who[{u, v}];
    for (int i = 0; i < m; i++) {
        for (int t = 0; t < 4; t++) {
            dist[i][t] = 1e9;
        }
    }
    set<pair<int, pair<int, int> > > ft;
    ft.insert({0, {start, 4}});
    while (!ft.empty()) {
        auto x = *ft.begin();
        ft.erase(x);
        int u = x.second.first;
        int id = x.second.second;
        for (auto h: g[u]) {
            int de = h.first;
            int kt = (h.second != id) + dist[u][id];
            if (dist[de][h.second] > kt) {
                ft.erase({dist[de][h.second], {de, h.second}});
                dist[de][h.second] = kt;
                ft.insert({dist[de][h.second], {de, h.second}});
            }
        }
    }
    int res = 1e9;
    for (int t = 0; t < 4; t++) {
        chkmin(res, dist[finish][t]);
    }
    cout << res << '\n';
    return 0;
}   

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70