Submission #868255

#	Time	Username	Problem	Language	Result	Execution time	Memory
868255		hgmhc	절취선 (JOI14_ho_t5)	C++17	20 / 100	207 ms	33952 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];

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);
			// cerr << "A sweep x:"<<i<<" y:["<<y1<<","<<y2<<"] " <<ds.sum(y1,y2) <<"\n";
			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);
			// cerr << "B sweep x:"<<i<<" y:["<<y1<<","<<y2<<"z] " << max(0,ds.sum(y1,y2)-1) << "\n";
			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();
	// cerr << "get_v: " << res << '\n';
	swap(ver,hor);
	res += sweep_v();
	// cerr << "get_v: " << res << '\n';
	return res;
}

int64_t get_e() {
	int64_t res = sweep_e();
	// cerr << "get_e: " << res << '\n';
	swap(ver,hor);
	res += sweep_e();
	// cerr << "get_e: " << res << '\n';
	return res;
}

void solve() {
	int64_t v = get_v() / 2LL;
	int64_t e = get_e();
	int64_t f = 1-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();
}

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