Submission #1114112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114112		Mike_Vu	절취선 (JOI14_ho_t5)	C++14	100 / 100	1002 ms	79552 KiB

2014_ho_t5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
#define y1 LNTD
#define pil pair<ll, int>

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct BIT{
    int n;
    vector<int> bit;
    void init(int _n = 0) {
        n = _n;
        bit.assign(n+1, 0);
    }
    void update(int k, int x) {
        while (k <= n) {
            bit[k] += x;
            k += k & (-k);
        }
    }
    int getsum(int k) {
        int res = 0;
        while (k > 0) {
            res += bit[k];
            k -= k & (-k);
        }
        return res;
    }
    int query(int l, int r) {
        return getsum(r)-getsum(l-1);
    }
};

struct DSU{
    int numcc = 0;
    vector<int> dsu;
    void init(int _n = 0) {
        numcc= _n;
        dsu.assign(numcc+1, -1);
    }
    int newnode() {
        ++numcc;
        dsu.pb(-1);
        return (int)dsu.size()-1;
    }
    int f(int u) {
        return dsu[u] < 0 ? u : dsu[u] = f(dsu[u]);
    }
    int join(int u, int v) {
        u = f(u);
        v = f(v);
        if (u == v) return 0;
        if (dsu[u] > dsu[v]) swap(u, v);
        dsu[u] += dsu[v];
        dsu[v] = u;
        --numcc;
        return u;
    }
};

struct SMT{
    DSU dsu;
    int trsz;
    vector<multiset<pil>> tr;
    int numcc() {
        return dsu.numcc;
    }
    void addnumcc() {
        ++dsu.numcc;
    }
    void init(int n = 0) {
        trsz = 1;
        dsu.newnode();
        --dsu.numcc;
        while (trsz < n) trsz <<= 1;
        tr.assign(trsz<<1, multiset<pil>());
    }
    void insval(int k, ll e) {
        int id = k+trsz-1;
        int curval = dsu.newnode();
        pil x = {e, curval};
        tr[id].insert(x);
        id >>= 1;
        while (id > 0) {
            tr[id].insert(x);
            id >>= 1;
        }
    }
    void delval(int k) {
        int id = k+trsz-1;
        pil x = (*tr[id].begin());
        tr[id].erase(tr[id].begin());
        id >>= 1;
        while (id > 0) {
            auto it = tr[id].lower_bound(x);
            if (it != tr[id].end() && (*it) == x) {
                tr[id].erase(it);
            }
            id >>= 1;
        }
    }
    void unite(int id, int &curmatch) {
//        cout << "unite " << id << "\n";
        while (tr[id].size() > 1) {
            auto it1 = tr[id].begin(), it2 = it1;
            ++it2;
            dsu.join((*it1).se, (*it2).se);
            tr[id].erase(it1);
        }
        if (tr[id].size() == 1) {
            int curid = (*tr[id].begin()).se;
            if (curmatch == 0) {
                curmatch = curid;
            }
            else dsu.join(curmatch, curid);
        }
//        cout << curmatch << "\n";
    }
    void query(int ql, int qr) {
//        cout << "query " << ql << ' ' << qr << "\n";
        int curmatch = 0;
        int l = ql+trsz-1, r = qr+trsz;
        while (l < r) {
            if (l&1) {
                unite(l++, curmatch);
            }
            if (r&1) {
                unite(--r, curmatch);
            }
            l >>= 1;
            r >>= 1;
        }
    }
//    void check() {
//        cout << "tree check " << numcc() << "\n";
//        for (int i= 1; i < trsz*2; i++) {
//            cout << "node " << i << ": ";
//            for (auto it = tr[i].begin(); it != tr[i].end(); it++) {
//                cout << (*it) << ' ';
//            }
//            cout << "\n";
//        }
//    }
};

struct event{
    int type; ///hori - vert
    int x, l;
    ll r;
    event(int _type, int _l, ll _r, int _x) {
        type = _type;
        l = _l;
        r = _r;
        x = _x;
    }
};
bool cmp1(event a, event b) {
    if (a.type != b.type) return a.type < b.type;
    if (a.x != b.x) return a.x < b.x;
    return a.l < b.l;
}
bool cmp2(event a, event b) {
    if (a.x != b.x) return a.x < b.x;
    if (a.type != b.type) return a.type > b.type;
    return a.r < b.r;
}

const int maxn = 1e5+5;
int n;
vector<event> e, cuts;
vector<int> values;
ll ans = 0;
BIT bit;
SMT tr;

int mp(int x){
    return lower_bound(values.begin(), values.end(), x)-values.begin()+1;
}

vector<event> discretize(vector<event> a){
    vector<event> af, res;
    //discretize
    sort(a.begin(), a.end(), cmp1);
    bool curtype = a[0].type;
    int curl = a[0].l, curr = a[0].r, curx = a[0].x;
    for (int i = 1; i < (int)a.size(); i++) {
        bool type = a[i].type;
        int l = a[i].l, r = a[i].r, x = a[i].x;
//        cout << type << ' ' << l << ' ' << r << ' ' << x << "\n";
        if ((type == curtype && x == curx) && l <= curr) {
            maximize(curr, r);
        }
        else {
            af.pb(event(curtype, curl, curr, curx));
            curtype = a[i].type;
            curl = a[i].l;
            curr = a[i].r;
            curx = a[i].x;
        }
    }
    af.pb(event(curtype, curl, curr, curx));
    //transform + values
    ll incval = maxn*3, sumval = 0;
    for (event cur : af) {
//        cout << cur.type << ' ' << cur.l << ' ' << cur.r << ' ' << cur.x << "\n";
        if (cur.type == 0) {
            values.pb(cur.x);
            ++sumval;
            res.pb(event(1, cur.x, (ll)cur.r*incval+sumval, cur.l));
            res.pb(event(-1, cur.x, (ll)cur.r*incval+sumval, cur.r));
        }
        else {
            values.pb(cur.l);
            values.pb(cur.r);
            res.pb(event(0, cur.l, cur.r, cur.x));
//            cout << res.back().l << "\n";
        }
    }
//    cout << "discretize completed\n";
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    return res;
}

void sweepline() {
    sort(e.begin(), e.end(), cmp2);
    bit.init((int)values.size());
    tr.init((int)values.size());
    ll sumv = 0, sume = 0;
    for (event cure : e) {
        int type = cure.type, l = cure.l;
        ll r = cure.r;
//        cout << "event " << type << ' ' << cure.x << ' ' << cure.l << ' ' << cure.r << "\n";
        if (type == 0) {
            //vertical
            int val = bit.query(mp(l), mp(r));
            if (val == 0) {
                //case not intersect
                ++sumv;
                tr.addnumcc();
            }
            else {
                sume += val-1;
                tr.query(mp(l), mp(r));
            }
        }
        else if (type == 1) {
            //new
            ++sumv;
            bit.update(mp(l), 1);
            tr.insval(mp(l), r);
        }
        else {
            bit.update(mp(l), -1);
            tr.delval(mp(l));
        }
//        tr.check();
    }
    //ans = e-v+c
//    cout << sume << ' ' << sumv << ' ' << tr.numcc() << "\n";
    ans = sume-sumv+tr.numcc();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int w, h;
    cin >> w >> h >> n;
    cuts.pb(event(0, 0, w, 0));
    cuts.pb(event(0, 0, w, h));
    cuts.pb(event(1, 0, h, 0));
    cuts.pb(event(1, 0, h, w));
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2 && y1 == y2) continue;
        if (x1 == x2) cuts.pb(event(1, y1, y2, x1));
        else cuts.pb(event(0, x1, x2, y1));
    }
    e = discretize(cuts);
    //sweepline
    sweepline();
    //active SMT, - waiting - set
    cout << ans;
}
/*
10 8 12
3 2 9 2
5 3 5 6
6 3 9 3
1 7 7 7
2 3 5 3
3 1 4 1
10 3 10 8
1 1 1 7
6 5 6 5
6 3 6 5
4 2 6 2
8 2 9 2
1

6 8 8
3 6 4 6
4 6 4 6
4 7 4 7
5 3 5 3
1 1 1 3
1 7 6 7
6 3 6 7
4 2 4 7
1

6 8 5
1 1 5 1
3 4 4 4
1 1 2 1
3 5 3 7
1 7 3 7
1

15 13 7
8 8 13 8
11 3 11 12
13 4 13 12
4 11 8 11
3 5 7 5
8 3 15 3
15 6 15 11
1
*/

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