Submission #1126871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126871		_callmelucian	절취선 (JOI14_ho_t5)	C++17	100 / 100	272 ms	43768 KiB

2014_ho_t5

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct BIT {
    vector<int> tr;
    BIT (int sz) : tr(sz + 3) {}

    int p (int k) { return k & -k; }

    void update (int k, int val) {
        for (++k; k < tr.size(); k += p(k)) tr[k] += val;
    }

    int preSum (int k, int ans = 0) {
        for (++k; k; k -= p(k)) ans += tr[k];
        return ans;
    }

    int query (int l, int r) { return preSum(r) - preSum(l - 1); }
};

struct DSU {
    vector<int> lab;
    int component;
    DSU (int sz) : lab(sz + 1, -1), component(sz) {}

    int get (int u) {
        if (lab[u] < 0) return u;
        return lab[u] = get(lab[u]);
    }

    void unite (int a, int b) {
//        cout << "try merge " << a << " " << b << "\n";
        a = get(a), b = get(b);
        if (a == b) return;
        if (-lab[a] < -lab[b]) swap(a, b);
        lab[a] += lab[b], lab[b] = a;
        component--;
    }
};

struct IT {
    vector<int> active, lazy;
    vector<bool> leaf;
    DSU dsu;

    void build (int k, int l, int r) {
        if (l == r) return leaf[k] = 1, void();
        int mid = (l + r) >> 1;
        build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
    }

    IT (int sz, int node) : active(4 * sz), lazy(4 * sz), leaf(4 * sz), dsu(node) { build(1, 0, sz); }

    void apply (int k, int val) {
        if (leaf[k]) {
            if (active[k]) dsu.unite(active[k], val);
        }
        else {
            if (active[k] && lazy[k]) dsu.unite(lazy[k], val);
            lazy[k] = val;
        }
    }

    void pushDown (int k) {
        if (lazy[k]) apply(k << 1, lazy[k]), apply(k << 1 | 1, lazy[k]), lazy[k] = 0;
    }

    void updateRange (int a, int b, int val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b) return apply(k, val), void();
        int mid = (l + r) >> 1; pushDown(k);
        updateRange(a, b, val, k << 1, l, mid);
        updateRange(a, b, val, k << 1 | 1, mid + 1, r);
        active[k] = active[k << 1] | active[k << 1 | 1];
    }

    void updatePoint (int pos, int val, int k, int l, int r) {
        for (; l < r;) {
            int mid = (l + r) >> 1; pushDown(k);
            if (pos <= mid) k <<= 1, r = mid;
            else k <<= 1, k |= 1, l = mid + 1;
        }
        active[k] = val, lazy[k] = 0;
        for (k >>= 1; k; k >>= 1)
            active[k] = active[k << 1] | active[k << 1 | 1];
    }

    int component() { return dsu.component; }
};

const int mn = 3e5 + 5;
vector<int> openSweep[mn], closeSweep[mn], cmpX, cmpY;
vector<pii> cutVert[mn], cutHorz[mn];

int getX (int x) { return lower_bound(all(cmpX), x) - cmpX.begin(); }
int getY (int y) { return lower_bound(all(cmpY), y) - cmpY.begin(); }

void refine (vector<pii> &vec) {
    sort(all(vec));
    vector<pii> lines;
    for (pii item : vec) {
        if (lines.empty() || lines.back().second < item.first) lines.push_back(item);
        else lines.back().second = max(lines.back().second, item.second);
    }
    swap(lines, vec);
}

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

    /// read input & compress coordinates
    int W, H, n; cin >> W >> H >> n;

    // general cuts
    vector<tpl> cuts(n);
    for (int i = 0; i < n; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        cuts[i] = make_tuple(a, b, c, d);
        cmpX.push_back(a), cmpY.push_back(b);
        cmpX.push_back(c), cmpY.push_back(d);
    }

    // edge cuts
    cuts.emplace_back(0, 0, W, 0);
    cuts.emplace_back(0, 0, 0, H);
    cuts.emplace_back(W, 0, W, H);
    cuts.emplace_back(0, H, W, H);

    // compress
    cmpX.push_back(0), cmpX.push_back(W);
    cmpY.push_back(0), cmpY.push_back(H);
    sort(all(cmpX)), filter(cmpX);
    sort(all(cmpY)), filter(cmpY);

    /// process intersecting cuts
    for (tpl &item : cuts) {
        int a, b, c, d; tie(a, b, c, d) = item;
        a = getX(a), b = getY(b), c = getX(c), d = getY(d);
        if (a == c) cutVert[a].emplace_back(min(b, d), max(b, d));
        if (b == d) cutHorz[b].emplace_back(min(a, c), max(a, c));
    }
    for (int x = 0; x < cmpX.size(); x++) refine(cutVert[x]);
    for (int y = 0; y < cmpY.size(); y++) refine(cutHorz[y]);

    /// create sweep-line events
    int compCount = 0, sz = cmpY.size();
    for (int y = 0; y < cmpY.size(); y++) {
        for (pii item : cutHorz[y]) {
            openSweep[item.first].push_back(y);
            closeSweep[item.second].push_back(y);
        }
        compCount += cutHorz[y].size();
    }
    for (int x = 0; x < cmpX.size(); x++) compCount += cutVert[x].size();

    /// sweep-line
    BIT tree(sz); IT comp(sz, compCount);
    ll counter = 0, vertices = 0, edges = 0;

    for (int x = 0; x < cmpX.size(); x++) {
        for (int y : openSweep[x]) {
            tree.update(y, 1), vertices++;
            comp.updatePoint(y, ++counter, 1, 0, sz);
//            cout << "open " << x << " " << y << " " << counter << "\n";
        }
        for (pii item : cutVert[x]) {
            int a, b; tie(a, b) = item;
            int intersect = tree.query(a, b);
            comp.updateRange(a, b, ++counter, 1, 0, sz);
//            cout << "range " << x << " " << a << " " << b << " " << counter << "\n";

            vertices += intersect + 2;
            edges += 2 * intersect + 2 - 1;
        }
        for (int y : closeSweep[x]) {
            tree.update(y, -1), vertices++, edges++;
            comp.updatePoint(y, 0, 1, 0, sz);
        }
    }
    assert(counter == compCount);

    /// Euler's polyhedron formula
//    cout << edges << " " << vertices << " " << comp.component() << "\n";
    cout << edges - vertices + comp.component() << "\n";

    return 0;
}

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