oj.uz

답안 #868255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
868255 2023-10-31T01:18:21 Z hgmhc 절취선 (JOI14_ho_t5) C++17
20 / 100
 207 ms 33952 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19804 KB Output is correct
2 Correct 17 ms 19876 KB Output is correct
3 Correct 17 ms 19804 KB Output is correct
4 Correct 17 ms 19804 KB Output is correct
5 Correct 17 ms 20056 KB Output is correct
6 Incorrect 17 ms 19888 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19804 KB Output is correct
2 Correct 17 ms 19876 KB Output is correct
3 Correct 17 ms 19804 KB Output is correct
4 Correct 17 ms 19804 KB Output is correct
5 Correct 17 ms 20056 KB Output is correct
6 Incorrect 17 ms 19888 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19804 KB Output is correct
2 Incorrect 17 ms 19804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 19804 KB Output is correct
2 Correct 18 ms 19784 KB Output is correct
3 Correct 32 ms 21176 KB Output is correct
4 Correct 20 ms 19804 KB Output is correct
5 Correct 18 ms 19804 KB Output is correct
6 Correct 207 ms 33952 KB Output is correct
7 Correct 24 ms 20924 KB Output is correct
8 Correct 124 ms 30112 KB Output is correct
9 Correct 114 ms 30652 KB Output is correct
10 Correct 110 ms 29900 KB Output is correct

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19804 KB Output is correct
2 Correct 17 ms 19876 KB Output is correct
3 Correct 17 ms 19804 KB Output is correct
4 Correct 17 ms 19804 KB Output is correct
5 Correct 17 ms 20056 KB Output is correct
6 Incorrect 17 ms 19888 KB Output isn't correct
7 Halted 0 ms 0 KB -