Submission #868625

#	Time	Username	Problem	Language	Result	Execution time	Memory
868625		hgmhc	절취선 (JOI14_ho_t5)	C++17	20 / 100	305 ms	38048 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 += max(0,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;
    	}
     
    }
     
    int p[4*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;
    }
     
    // 5 4 9
    // 0 1 2 1
    // 3 1 4 1
    // 1 0 1 3
    // 0 2 4 2
    // 3 3 3 1
    // 4 1 4 0
    // 3 3 4 3
    // 4 2 4 3
    // 2 1 2 4
    // answer: 7
     
    // [a,b]에 뭐라도 남아있다면, 양 자식에 레이지 밀어서 합치기
    // [a,b]에 아무것도 없으면, 레이지를 보존할 이유 없음
     
    template <const int N=1<<18>
    struct segtree {
    	int t[2*N]{}, sum[2*N]{};
    	segtree(){ iota(p,p+4*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]=sum[2*k]+sum[2*k+1];
    	}
    	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 = get_c()-v+e;
    	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 merge(int, int)':
2014_ho_t5.cpp:93:10: warning: unused variable 'x' [-Wunused-variable]
   93 |      int x=a, y=b;
      |          ^
2014_ho_t5.cpp:93:15: warning: unused variable 'y' [-Wunused-variable]
   93 |      int x=a, y=b;
      |               ^

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