oj.uz

답안 #122462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122462 2019-06-28T11:06:20 Z egorlifar Golf (JOI17_golf) C++17
10 / 100
 3367 ms 1048576 KB 
/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#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});
    }
    for (int i = 0; i < sz(vx); i++) {
        for (int j = 0; j < sz(vy); j++) {
            st.insert({i, j});
        }
    }
    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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 52224 KB Output is correct
2 Correct 36 ms 52224 KB Output is correct
3 Correct 37 ms 52224 KB Output is correct
4 Correct 135 ms 61044 KB Output is correct
5 Correct 2886 ms 206244 KB Output is correct
6 Correct 3191 ms 201648 KB Output is correct
7 Correct 2726 ms 197524 KB Output is correct
8 Correct 3316 ms 209040 KB Output is correct
9 Correct 3367 ms 206388 KB Output is correct
10 Correct 3263 ms 210256 KB Output is correct
11 Correct 2888 ms 217972 KB Output is correct
12 Correct 2755 ms 213992 KB Output is correct
13 Correct 3218 ms 212272 KB Output is correct
14 Correct 2787 ms 209336 KB Output is correct
15 Correct 561 ms 84432 KB Output is correct
16 Correct 2371 ms 180108 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 52224 KB Output is correct
2 Correct 36 ms 52224 KB Output is correct
3 Correct 37 ms 52224 KB Output is correct
4 Correct 135 ms 61044 KB Output is correct
5 Correct 2886 ms 206244 KB Output is correct
6 Correct 3191 ms 201648 KB Output is correct
7 Correct 2726 ms 197524 KB Output is correct
8 Correct 3316 ms 209040 KB Output is correct
9 Correct 3367 ms 206388 KB Output is correct
10 Correct 3263 ms 210256 KB Output is correct
11 Correct 2888 ms 217972 KB Output is correct
12 Correct 2755 ms 213992 KB Output is correct
13 Correct 3218 ms 212272 KB Output is correct
14 Correct 2787 ms 209336 KB Output is correct
15 Correct 561 ms 84432 KB Output is correct
16 Correct 2371 ms 180108 KB Output is correct
17 Runtime error 2655 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 52224 KB Output is correct
2 Correct 36 ms 52224 KB Output is correct
3 Correct 37 ms 52224 KB Output is correct
4 Correct 135 ms 61044 KB Output is correct
5 Correct 2886 ms 206244 KB Output is correct
6 Correct 3191 ms 201648 KB Output is correct
7 Correct 2726 ms 197524 KB Output is correct
8 Correct 3316 ms 209040 KB Output is correct
9 Correct 3367 ms 206388 KB Output is correct
10 Correct 3263 ms 210256 KB Output is correct
11 Correct 2888 ms 217972 KB Output is correct
12 Correct 2755 ms 213992 KB Output is correct
13 Correct 3218 ms 212272 KB Output is correct
14 Correct 2787 ms 209336 KB Output is correct
15 Correct 561 ms 84432 KB Output is correct
16 Correct 2371 ms 180108 KB Output is correct
17 Runtime error 2655 ms 1048576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -