Submission #868618

#	Time	Username	Problem	Language	Result	Execution time	Memory
868618		hgmhc	절취선 (JOI14_ho_t5)	C++17	20 / 100	283 ms	35492 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[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;
}

// 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]에 뭐라도 남아있다면,
// 양 자식에 레이지 합치기

template <const int N=1<<18>
struct segtree {
	int t[2*N]{}, sum[2*N]{};
	segtree(){ iota(p,p+2*M,0); }
	void insert(int i, int c, int k, int s, int e) {
		if (s == i and i == e) { t[k] = c; return; }
		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;
		int m = (s+e)/2;
		if (i <= m) insert(i,c,2*k,s,m);
		else insert(i,c,2*k+1,m+1,e);
	}
	void insert(int i, int c) {
		insert(i,c,1,0,N-1);
		assert(!sum[i+=N]);
		for (; i >= 1; i /= 2) sum[i]++;
	}
	void erase(int i) {
		int c = t[i+=N];
		assert(sum[i]), t[i] = 0;
		for (; i >= 1; i /= 2) sum[i]--, c = merge(c,t[i]);
	}
	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.insert(y,++clr);
		for (auto [y1,y2] : ver[i]) {
			if (y1 > y2) swap(y1,y2);
			ds.join(y1,y2,++clr);
		}
		for (auto y : out[i]) ds.erase(y);
		// 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:6: warning: unused variable 'x' [-Wunused-variable]
   93 |  int x=a, y=b;
      |      ^
2014_ho_t5.cpp:93:11: 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