Submission #1068561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068561		juicy	Golf (JOI17_golf)	C++17	100 / 100	3447 ms	326316 KiB

golf

// https://oj.uz/submission/404188

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

struct Segtree {
    int n;
    vector<set<array<int, 3>>> s;

    Segtree() {};

    Segtree(int n): n(n), s(4 << __lg(n)) {};

    void add(int i, int u, int v, int id, int l, int r) {
        if (u <= l && r <= v) {
            s[id].insert({i, u, v});
            return;
        }
        int md = (l + r) / 2;
        if (u <= md) {
            add(i, u, v, id * 2, l, md);
        }
        if (md < v) {
            add(i, u, v, id * 2 + 1, md + 1, r);
        }
    }

    void add(int i, int l, int r) {
        add(i, l, r, 1, 1, n);
    }

    void gather(int i, int u, int v, vector<array<int, 3>> &graph, int id, int l, int r) {
        for (auto it = s[id].lower_bound(array<int, 3>{u}); it != s[id].end() && (*it)[0] <= v; it = s[id].erase(it)) {
            graph.push_back(*it);
        }
        if (l == r) {
            return;
        }
        int md = (l + r) / 2;
        if (i <= md) {
            gather(i, u, v, graph, id * 2, l, md);
        } else {
            gather(i, u, v, graph, id * 2 + 1, md + 1, r);
        }
    }

    vector<array<int, 3>> qry(int i, int u, int v) {
        vector<array<int, 3>> graph;
        gather(i, u, v, graph, 1, 1, n);
        return graph;
    }
} tree[2];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    const int inf = 1e9 + 7;
    
    array<vector<int>, 2> comp;
    for (auto it : {0, 1}) {
        comp[it] = vector{0, inf};
    }
    auto add = [&](array<int, 2> pt) {
        for (auto it : {0, 1}) {
            comp[it].push_back(pt[it]);
        }
    };
    auto get = [&](array<int, 2> x) {
        for (auto it : {0, 1}) {
            x[it] = lower_bound(comp[it].begin(), comp[it].end(), x[it]) - comp[it].begin() + 1;
        }
        return x;
    };
    array<int, 2> s, t;
    cin >> s[0] >> s[1] >> t[0] >> t[1];
    add(s), add(t);
    int n; cin >> n;
    array<vector<array<int, 3>>, 2> events;
    while (n--) {
        array<int, 2> a, b;
        cin >> a[0] >> b[0] >> a[1] >> b[1];
        add(a); add(b);
        for (auto it : {0, 1}) {
            for (auto x : {a[it], b[it]}) {
                events[it ^ 1].push_back({a[it ^ 1], 1, x});
                events[it ^ 1].push_back({b[it ^ 1], -1, x});
                events[it].push_back({x, 0, a[it ^ 1]});
            }
        }
    }
    for (auto it : {0, 1}) {
        sort(comp[it].begin(), comp[it].end());
        comp[it].erase(unique(comp[it].begin(), comp[it].end()), comp[it].end());
    }
    for (auto it : {0, 1}) {
        for (auto &x : events[it]) {
            x[0] = lower_bound(comp[it].begin(), comp[it].end(), x[0]) - comp[it].begin() + 1;
            x[2] = lower_bound(comp[it ^ 1].begin(), comp[it ^ 1].end(), x[2]) - comp[it ^ 1].begin() + 1;
        }
    }
    s = get(s), t = get(t);
    for (int i = 0; i < 2; ++i) {
        events[i].push_back({s[i], 0, s[i ^ 1]});
        events[i].push_back({t[i], 0, t[i ^ 1]});
        tree[i] = Segtree(comp[i].size());
    }
    for (auto it : {0, 1}) {
        sort(events[it].begin(), events[it].end());
        set<int> st{1, comp[it ^ 1].size()};
        for (auto [a, t, b] : events[it]) {
            if (t == 1) {
                st.insert(b);
            } else if (t == -1) {
                st.erase(b);
            } else {
                auto i = st.lower_bound(b);
                int r = *i, l = *--i;
                tree[it ^ 1].add(a, l, r);
            }
        }
    }
    queue<array<int, 4>> q;
    map<array<int, 4>, int> mp;
    for (auto it : {0, 1}) {
        auto cands = tree[it ^ 1].qry(s[it ^ 1], s[it], s[it]);
        for (auto [x, u, v] : cands) {
            mp[{it, x, u, v}] = 1;
            q.push({it, x, u, v});
        }
    }
    while (q.size()) {
        auto [it, x, u, v] = q.front(); q.pop();
        int d = mp[{it, x, u, v}];
        if (t[it] == x && u <= t[it ^ 1] && t[it ^ 1] <= v) {
            cout << d;
            exit(0);
        }
        auto cands = tree[it].qry(x, u, v);
        for (auto [a, b, c] : cands) {
            if (!mp.count({it ^ 1, a, b, c})) {
                mp[{it ^ 1, a, b, c}] = d + 1;
                q.push({it ^ 1, a, b, c}); 
            }
        }
    }
    return 0;
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:116:41: warning: narrowing conversion of '(& comp.std::array<std::vector<int>, 2>::operator[](((std::array<std::vector<int>, 2>::size_type)(it ^ 1))))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  116 |         set<int> st{1, comp[it ^ 1].size()};
      |                        ~~~~~~~~~~~~~~~~~^~
golf.cpp:116:41: warning: narrowing conversion of '(& comp.std::array<std::vector<int>, 2>::operator[](((std::array<std::vector<int>, 2>::size_type)(it ^ 1))))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]

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