Submission #914138

#	Time	Username	Problem	Language	Result	Execution time	Memory
914138		Alcabel	절취선 (JOI14_ho_t5)	C++17	100 / 100	515 ms	36548 KiB

2014_ho_t5

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    int n;
    vector<int> par, sz, mask;
    DSU() {}
    DSU(int _n) {
        n = _n;
        par.resize(n);
        sz.resize(n);
        mask.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i, sz[i] = 1;
        }
    }
    int getParent(int v) {
        if (par[v] != v) {
            par[v] = getParent(par[v]);
        }
        return par[v];
    }
    void uniteSets(int v, int u) {
        // cerr << "v: " << v << ", u: " << u << '\n';
        v = getParent(v), u = getParent(u);
        if (v == u) { return; }
        if (sz[v] < sz[u]) { swap(v, u); }
        par[u] = v;
        sz[v] += sz[u];
        mask[v] |= mask[u];
    }
    int getComps() {
        int comps = 0;
        for (int i = 0; i < n; ++i) {
            if (getParent(i) == i && mask[i] == 3) {
                ++comps;
            }
        }
        return comps;
    }
    ~DSU() {}
};

struct SegTree {
    int n, N;
    DSU dsu;
    vector<int> lazy, sum;
    vector<set<int>> leafs;
    SegTree() {}
    SegTree(int _n, int dsusz) {
        n = _n, N = 1;
        while (N < n) {
            N <<= 1;
        }
        dsu = DSU(dsusz);
        lazy.resize(2 * N, -1);
        sum.resize(2 * N);
        leafs.resize(N);
    }
    void push(int v) {
        if (v < N) {
            if (lazy[2 * v] != -1 && sum[2 * v] > 0) {
                // cerr << "pushL\n";
                // cerr << v << '\n';
                dsu.uniteSets(lazy[2 * v], lazy[v]);
            }
            if (lazy[2 * v + 1] != -1 && sum[2 * v + 1] > 0) {
                // cerr << "pushR\n";
                // cerr << v << '\n';
                dsu.uniteSets(lazy[2 * v + 1], lazy[v]);
            }
            lazy[2 * v] = lazy[v];
            lazy[2 * v + 1] = lazy[v];
        } else {
            if (!leafs[v - N].empty()) {
                // cerr << "pushLeaf\n";
                dsu.uniteSets(lazy[v], *leafs[v - N].begin());
            }
        }
        lazy[v] = -1;
    }
    void unite(int v, int tl, int tr, int l, int r, int i) {
        if (lazy[v] != -1) {
            push(v);
        }
        if (tl >= r || tr <= l) {
            return;
        }
        if (l <= tl && tr <= r) {
            lazy[v] = i;
            push(v);
            return;
        }
        int m = tl + (tr - tl) / 2;
        unite(2 * v, tl, m, l, r, i);
        unite(2 * v + 1, m, tr, l, r, i);
    }
    void unite(int l, int r, int i) {
        unite(1, 0, N, l, r, i);
    }
    void change(int v, int tl, int tr, int pos, int i, int flag) {
        if (lazy[v] != -1) {
            push(v);
        }
        if (tl >= pos + 1 || tr <= pos) {
            return;
        }
        if (tl + 1 == tr) {
            if (flag > 0) {
                // insert
                if (!leafs[v - N].empty()) {
                    // cerr << "when change\n";
                    dsu.uniteSets(*leafs[v - N].begin(), i);
                }
                leafs[v - N].emplace(i);
            } else {
                // erase
                leafs[v - N].erase(i);
            }
            sum[v] = !leafs[v - N].empty();
            return;
        }
        int m = tl + (tr - tl) / 2;
        change(2 * v, tl, m, pos, i, flag);
        change(2 * v + 1, m, tr, pos, i, flag);
        sum[v] = sum[2 * v] + sum[2 * v + 1];
    }
    void change(int pos, int i, int flag) {
        change(1, 0, N, pos, i, flag);
    }
    int getSum(int l, int r) {
        if (l > r) { return 0; }
        int vl = N + l, vr = N + r, res = 0;
        while (vl < vr) {
            if (vl & 1) {
                res += sum[vl];
            }
            if ((vr ^ 1) & 1) {
                res += sum[vr];
            }
            vl = (vl + 1) >> 1;
            vr = (vr - 1) >> 1;
        }
        if (vl == vr) {
            res += sum[vl];
        }
        return res;
    }
    ~SegTree() {}
};

struct Event {
    int lx, rx, y, type, i;
    Event() {}
    Event(int _lx, int _rx, int _y, int _type, int _i) {
        lx = _lx, rx = _rx, y = _y, type = _type, i = _i;
    }
    bool operator<(const Event& other) const {
        return make_pair(y, type) < make_pair(other.y, other.type);
    }
    ~Event() {}
};

void solve() {
    int w, h, n;
    cin >> w >> h >> n;
    vector<vector<int>> cuts(n + 4, vector<int>(4));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) {
            cin >> cuts[i][j];
        }
    }
    cuts[n] = {0, 0, 0, h};
    cuts[n + 1] = {0, h, w, h};
    cuts[n + 2] = {w, 0, w, h};
    cuts[n + 3] = {0, 0, w, 0};
    n += 4;
    for (int i = 0; i < n; ++i) {
        if (cuts[i][0] == cuts[i][2] && cuts[i][1] == cuts[i][3]) {
            swap(cuts[i], cuts.back());
            cuts.pop_back();
            --i;
            --n;
        }
    }
    vector<Event> evs;
    vector<int> allX;
    auto getX = [&](int x) {
        return lower_bound(allX.begin(), allX.end(), x) - allX.begin();
    };
    auto calc = [&]() -> vector<long long> {
        SegTree st(allX.size(), n);
        for (int i = 0; i < n; ++i) {
            if (cuts[i][0] == cuts[i][2]) {
                st.dsu.mask[i] = 1;
            } else {
                st.dsu.mask[i] = 2;
            }
        }
        set<pair<int, int>> segs;
        vector<long long> res = {0, 0, 0};
        for (int l = 0; l < (int)evs.size(); ++l) {
            if (evs[l].type == 0) {
                segs.clear();
                int r = l - 1;
                while (r + 1 < (int)evs.size() && evs[r + 1].type == 0 && evs[r + 1].y == evs[l].y) {
                    ++r;
                    st.unite(getX(evs[r].lx), getX(evs[r].rx) + 1, evs[r].i);
                    int newL = evs[r].lx, newR = evs[r].rx;
                    auto it = segs.lower_bound(make_pair(evs[r].lx, 0));
                    while (it != segs.end() && it->second <= evs[r].rx) {
                        newL = min(newL, it->second);
                        newR = max(newR, it->first);
                        it = segs.erase(it);
                    }
                    segs.emplace(newR, newL);
                }
                while (!segs.empty()) {
                    auto [rx, lx] = *segs.begin();
                    segs.erase(segs.begin());
                    int ptrL = getX(lx), ptrR = getX(rx), points;
                    points = st.getSum(ptrL, ptrR);
                    // cerr << "y: " << evs[r].y << ", lx: " << lx << ", rx: " << rx << ", points: " << points << '\n';
                    res[0] += points, res[1] += max(0, points - 1);
                }
                l = r;
            } else {
                // cerr << "y: " << evs[l].y << ", x: " << evs[l].lx << ", type: " << evs[l].type << '\n';
                st.change(getX(evs[l].lx), evs[l].i, -evs[l].type);
            }
        }
        res[2] = st.dsu.getComps();
        cerr << "res: " << res[0] << ' ' << res[1] << ' ' << res[2] << '\n';
        return res;
    };
    vector<long long> res = {-1, 0, -1};
    for (int iter = 0; iter < 2; ++iter) {
        allX.clear();
        evs.clear();
        for (int i = 0; i < n; ++i) {
            if (cuts[i][0] == cuts[i][2]) {
                // vertical
                evs.emplace_back(cuts[i][0], cuts[i][0], cuts[i][1], -1, i);
                evs.emplace_back(cuts[i][0], cuts[i][0], cuts[i][3], 1, i);
                allX.emplace_back(cuts[i][0]);
            } else {
                // horizontal
                evs.emplace_back(cuts[i][0], cuts[i][2], cuts[i][1], 0, i);
                allX.emplace_back(cuts[i][0]);
                allX.emplace_back(cuts[i][2]);
            }
        }
        sort(allX.begin(), allX.end());
        allX.resize(unique(allX.begin(), allX.end()) - allX.begin());
        sort(evs.begin(), evs.end());
        vector<long long> tmp = calc();
        assert(res[0] == -1 || res[0] == tmp[0]);
        assert(res[2] == -1 || res[2] == tmp[2]);
        res[0] = tmp[0], res[2] = tmp[2];
        res[1] += tmp[1];
        for (int i = 0; i < n; ++i) {
            swap(cuts[i][0], cuts[i][1]);
            swap(cuts[i][2], cuts[i][3]);
        }
    }
    cout << res[1] - res[0] + res[2] << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50