Submission #1139630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139630		ConquerConquerer	절취선 (JOI14_ho_t5)	C++20	100 / 100	345 ms	26020 KiB

2014_ho_t5

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

const int maxN = 1e5 + 10;

struct Qr {
    int num, type, L, R;

    bool operator < (const Qr& rhs) const {
        if (num != rhs.num) return num < rhs.num;
        return type < rhs.type;
    }
} query[3 * maxN];

namespace DSU {
    int par[maxN], sz[maxN], num_tplt, ON[maxN];

    void init(int n) {
        num_tplt = n;
        for (int i = 1; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find_set(int u) {
        return (par[u] == u) ? u : par[u] = find_set(par[u]);
    }

    void union_set(int u, int v) {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return ;
        num_tplt--;
        if (sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
    }
}

namespace sum{
    int BIT[maxN];

    void update(int pos, int val, int n) {
        int p = pos;
        while (p <= n) {
            BIT[p] += val;
            p += p & (-p);
        }
    }

    int getSum(int pos) {
        int p = pos, ans = 0;
        while (p) {
            ans += BIT[p];
            p -= p & (-p);
        }
        return ans;
    }

    int getRange(int L, int R) {
        if (L > R) return 0;
        return getSum(R) - getSum(L - 1);
    }
}

vector<int> posX, posY;
int A[maxN], B[maxN], C[maxN], D[maxN];

map<pair<int, int>, int> belong_to;
set<pair<int, int>> save;

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

    int W, H, n;
    cin >> W >> H >> n;

    posX.push_back(0); posX.push_back(W);
    posY.push_back(0); posY.push_back(H);
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];

        posX.push_back(A[i]); posX.push_back(C[i]);
        posY.push_back(B[i]); posY.push_back(D[i]);
    }
    //cout << '\n';

    sort(posX.begin(), posX.end());
    posX.erase(unique(posX.begin(), posX.end()), posX.end());

    sort(posY.begin(), posY.end());
    posY.erase(unique(posY.begin(), posY.end()), posY.end());

    //for (auto v: posX) cout << v << ' '; cout << '\n';
    //for (auto v: posY) cout << v << ' '; cout << '\n';

    A[n + 1] = 0; B[n + 1] = 0; C[n + 1] = 0; D[n + 1] = H;
    A[n + 2] = 0; B[n + 2] = H; C[n + 2] = W; D[n + 2] = H;
    A[n + 3] = W; B[n + 3] = 0; C[n + 3] = W; D[n + 3] = H;
    A[n + 4] = 0; B[n + 4] = 0; C[n + 4] = W; D[n + 4] = 0;
    n += 4; int M = posY.size();

    int Q = 0;
    for (int i = 1; i <= n; i++) {
        A[i] = lower_bound(posX.begin(), posX.end(), A[i]) - posX.begin() + 1;
        C[i] = lower_bound(posX.begin(), posX.end(), C[i]) - posX.begin() + 1;
        B[i] = lower_bound(posY.begin(), posY.end(), B[i]) - posY.begin() + 1;
        D[i] = lower_bound(posY.begin(), posY.end(), D[i]) - posY.begin() + 1;
        //cout << "line " << A[i] << ' ' << B[i] << ' ' << C[i] << ' ' << D[i] << '\n';

        if (A[i] == C[i]) query[++Q] = {A[i], i, B[i], D[i]};
        else {
            query[++Q] = {A[i], 0, B[i], i};
            query[++Q] = {C[i], 1000000, B[i], i};
        }
    }

    DSU::init(n);
    sort(query + 1, query + Q + 1);
    long long ans = 0;
    for (int i = 1; i <= Q; i++) {
        auto [num, type, L, R] = query[i];
        //cout << num << ' ' << type << ' ' << L << ' ' << R << ' ' << "idx = " << ((type > 0) ? type : R) << '\n';

        if (type == 0) { /// Add a line
            int idx = R, pos = L;
            sum::update(pos, 1, M);

            auto it = save.upper_bound({pos, 1e9});
            if (it != save.begin()) {
                it--;
                auto [lt, rt] = *it; int org = belong_to[{lt, rt}];
                if (lt <= pos && pos <= rt) {
                    save.erase(it);
                    if (sum::getRange(lt, pos - 1)) {
                        belong_to[{lt, pos - 1}] = org;
                        save.insert({lt, pos - 1});
                    }
                    if (sum::getRange(pos + 1, rt)) {
                        belong_to[{pos + 1, rt}] = org;
                        save.insert({pos + 1, rt});
                    }
                }
            }

            save.insert({pos, pos});
            belong_to[{pos, pos}] = idx;
        }
        else if (type == 1000000) { /// Remove a line
            int idx = R, pos = L;
            sum::update(pos, -1, M);

            auto it = save.upper_bound({pos, 1e9});
            if (it != save.begin()) {
                it--;
                auto [lt, rt] = *it;
                if (lt <= pos && pos <= rt)
                    if (!sum::getRange(lt, rt))
                        save.erase(it);
            }
        }
        else { /// Query A Range
            int bonus = sum::getRange(L, R); /// Number of line between L and R
            if (bonus) {
                ans += bonus;
                pair<int, int> asking = {R, 1e9};
                auto it = save.upper_bound(asking); /// DSU section
                int low = 2e9, high = -1;
                while (it != save.begin()) {
                    it--; pair<int, int> X = *it;
                    if (X.second < L) break;

                    if (sum::getRange(max(L, X.first), min(R, X.second))) {
                        save.erase(it);
                        low = min(low, X.first);
                        high = max(high, X.second);
                        DSU::union_set(belong_to[X], type);
                    }
                    else asking = X;

                    if (save.size() == 0) break;
                    it = save.lower_bound(asking);
                }

                if (high != -1) {
                    save.insert({low, high});
                    belong_to[{low, high}] = DSU::find_set(type);
                }
            }
        }

        //cout << DSU::num_tplt << '\n';
        //for (int i = 1; i <= n; i++)
            //cout << DSU::find_set(i) << ' ';
        //cout << '\n';
        //for (auto it = save.begin(); it != save.end(); it++) {
            //pair<int, int> X = *it;
            //cout << "( " << X.first << ' ' << X.second << " )\n";
        //}
        //cout << '\n';
    }

    //cout << ans << '\n';
    cout << ans + DSU::num_tplt - n;
    return 0;
}

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