Submission #868635

#	Time	Username	Problem	Language	Result	Execution time	Memory
868635		hgmhc	절취선 (JOI14_ho_t5)	C++17	100 / 100	317 ms	40320 KiB

2014_ho_t5

#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
using namespace std;
    
const int M = 2e5+10;
int w, h, n;
vector<pair<int,int>> ver[M], hor[M];
    
namespace sub4 {
    
    template <const int N>
    struct fenwick {
        int t[N+1]{};
        void add(int k, int x) {
            for (++k; k <= N; k += k&-k) t[k] += x;
        }
        int sum(int a, int b) {
            int r = 0;
            for (; a >= 1; a -= a&-a) r -= t[a];
            for (++b; b >= 1; b -= b&-b) r += t[b];
            return r;
        }
    };
    
    fenwick<M> ds;
    
    int64_t sweep_v() {
        // 꼭짓점 말고 교차점만 카운트
        vector<int> in[M], out[M];
        rep(i,0,M-1) {
            for (auto [x1,x2] : hor[i]) {
                if (x1 > x2) swap(x1,x2);
                in[x1].push_back(i);
                out[x2].push_back(i);
            }
        }
        int64_t res = 0;
        rep(i,0,M-1) {
            for (auto y : in[i]) ds.add(y,+1);
            for (auto [y1,y2] : ver[i]) {
                if (y1 > y2) swap(y1,y2);
                res += ds.sum(y1,y2);
            }
            for (auto y : out[i]) ds.add(y,-1);
        }
        return res;
    }
    
    int64_t sweep_e() {
        // 선분마다 꼭짓점은 무시하고 교차점-1로 카운트
        vector<int> in[M], out[M];
        rep(i,0,M-1) {
            for (auto [x1,x2] : hor[i]) {
                if (x1 > x2) swap(x1,x2);
                in[x1].push_back(i);
                out[x2].push_back(i);
            }
        }
        int64_t res = 0;
        rep(i,0,M-1) {
            for (auto y : in[i]) ds.add(y,+1);
            for (auto [y1,y2] : ver[i]) {
                if (y1 > y2) swap(y1,y2);
                res += ds.sum(y1,y2)-1;
            }
            for (auto y : out[i]) ds.add(y,-1);
        }
        return res;
    }
    
    int64_t get_v() {
        int64_t res = sweep_v();
        swap(ver,hor);
        res += sweep_v();
        return res;
    }
    
    int64_t get_e() {
        int64_t res = sweep_e();
        swap(ver,hor);
        res += sweep_e();
        return res;
    }
    
}

namespace sub5 {

    int p[2*M], cnt=0;
    int find(int x) {
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }
    int merge(int a, int b) {
        int x=a, y=b;
        if (a == 0) return b;
        if (b == 0) return a;
        a = find(a), b = find(b);
        if (a == b) return a;
        // cerr << x << ' ' << y << endl;
        cnt++;
        p[b] = a;
        return a;
    }

    // [a,b]에 뭐라도 남아있다면, 양 자식에 레이지 밀어서 합치기
    // [a,b]에 아무것도 없으면, 레이지를 보존할 이유 없음

    template <const int N=1<<18>
    struct segtree {
        int t[2*N]{}, sum[2*N]{};
        segtree(){ iota(p,p+2*M,0); }
        void prop(int k) {
            if (k < N) {
                if (sum[2*k]) t[2*k] = merge(t[2*k],t[k]);
                if (sum[2*k+1]) t[2*k+1] = merge(t[2*k+1],t[k]);
            }
            t[k]=0;
        }
        void update(int i, int c, int d, int k=1, int s=0, int e=N-1) {
            prop(k);
            if (s == i and i == e) { t[k] = c, sum[k]+=d; return; }
            int m = (s+e)/2;
            if (i <= m) update(i,c,d,2*k,s,m);
            else update(i,c,d,2*k+1,m+1,e);
            sum[k]+=d;
        }
        void join(int a, int b, int c) {
            for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
                if (a&1) {
                    if (sum[a]) merge(c,t[a]);
                    t[a]=c;
                }
                if (~b&1) {
                    if (sum[b]) merge(c,t[b]);
                    t[b]=c;
                }
            }
        }
    };
    
    segtree<> ds;
    
    int64_t get_c() {
        vector<int> in[M], out[M];
        rep(i,0,M-1) {
            for (auto [x1,x2] : hor[i]) {
                if (x1 > x2) swap(x1,x2);
                in[x1].push_back(i);
                out[x2].push_back(i);
            }
        }
        int clr = 0;
        rep(i,0,M-1) {
            for (auto y : in[i]) ds.update(y,++clr,+1);
            for (auto [y1,y2] : ver[i]) {
                if (y1 > y2) swap(y1,y2);
                ds.join(y1,y2,++clr);
            }
            for (auto y : out[i]) ds.update(y,0,-1);
            // cerr << clr << ' ' << cnt << endl;
        }
        return clr-cnt;
    }
}

void solve() {
    int64_t v = sub4::get_v() / 2LL;
    int64_t e = sub4::get_e();
    int64_t f = sub5::get_c()-v+e;
    // fprintf(stderr,"v=%lld, e=%lld, f=%lld",v,e,f);
    cout << f;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> w >> h >> n;
    vector<array<int,4>> segments(n);
    vector<int> xs, ys;
    xs.push_back(0), xs.push_back(w);
    ys.push_back(0), ys.push_back(h);
    for (auto &[a,b,c,d] : segments) {
        cin >> a >> b >> c >> d;
        xs.push_back(a), xs.push_back(c);
        ys.push_back(b), ys.push_back(d);
    }
    segments.push_back({w,0,0,0});
    segments.push_back({w,h,0,h});
    segments.push_back({w,0,w,h});
    segments.push_back({0,h,0,0});
    sort(begin(xs),end(xs)), xs.erase(unique(begin(xs),end(xs)),end(xs));
    sort(begin(ys),end(ys)), ys.erase(unique(begin(ys),end(ys)),end(ys));
    for (auto &[a,b,c,d] : segments) {
        a = lower_bound(begin(xs),end(xs),a)-begin(xs);
        b = lower_bound(begin(ys),end(ys),b)-begin(ys);
        c = lower_bound(begin(xs),end(xs),c)-begin(xs);
        d = lower_bound(begin(ys),end(ys),d)-begin(ys);
        // cerr << a << ' ' << b << ' ' << c << ' ' << d << endl;
        if (a == c) {
            ver[a].push_back({b,d});
        } else {
            hor[b].push_back({a,c});
        }
    }
    solve();
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int sub5::merge(int, int)':
2014_ho_t5.cpp:95:13: warning: unused variable 'x' [-Wunused-variable]
   95 |         int x=a, y=b;
      |             ^
2014_ho_t5.cpp:95:18: warning: unused variable 'y' [-Wunused-variable]
   95 |         int x=a, y=b;
      |                  ^

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