Submission #1354973

#TimeUsernameProblemLanguageResultExecution timeMemory
1354973jjwdi0수족관 2 (KOI13_aqua2)C++20
0 / 100
48 ms6092 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {
	vector<int> tree;
	int N;
	void init(int x) {
		N = x;
		tree = vector(N + 1, 0);
	}

	void add(int x, int y) {
		while (x <= N) {
			tree[x] += y;
			x += x & -x;
		}
	}

	int query(int x) {
		int res = 0;
		while (x) {
			res += tree[x];
			x -= x & -x;
		}
		return res;
	}
} bit;

struct SegTree {
	vector<pair<int, int>> tree;
	int N;
	void init(int x) {
		N = x;
		tree = vector<pair<int, int>>(N * 4 + 1);
	}

	void build(vector<pair<int, int>> &v) {
		build(1, 1, N, v);
	}
	void build(int node, int s, int e, vector<pair<int, int>> &v) {
		if (s == e) {
			tree[node] = {v[s].first, s};
			return;
		}
		int mid = (s + e) / 2;
		build(node * 2, s, mid, v);
		build(node * 2 + 1, mid + 1, e, v);
		tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
	}

	int query(int l, int r) {
		return query(1, 1, N, l, r).second;
	}
	pair<int, int> query(int node, int s, int e, int l, int r) {
		if (e < l || r < s)
			return {2e9, 0};
		if (l <= s && e <= r)
			return tree[node];
		int mid = (s + e) / 2;
		return min(query(node * 2, s, mid, l, r), query(node * 2 + 1, mid + 1, e, l, r));
	}
} seg_tree;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;
	vector<pair<int, int>> A(N / 2 + 1);
	ll ans1 = 0;
	int px = 0, py = 0;
	for (int i = 1, x1, y1, x2, y2; i <= N / 2; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		A[i] = {y2, x1};
		ans1 += 1LL * (x1 - px) * py;
		px = x1, py = y2;
	}

	seg_tree.init(N / 2);
	seg_tree.build(A);
	long double ans2 = 0;
	auto f = [&](auto&& self, int s, int e, int v) -> void {
		if (s > e)
			return;
		int c = bit.query(e) - bit.query(s - 1);
		if (c == 0)
			return;
		assert(s == e && c == 1);
		int idx = seg_tree.query(s, e);
		ll w = 1LL * (A[idx].first - v) * (A[e + 1].second - A[s].second);
		ans1 -= w;
		ans2 += (long double)w / c;
		self(self, s, idx - 1, A[idx].first);
		self(self, idx + 1, e, A[idx].first);
	};
	int K;
	cin >> K;
	bit.init(N / 2);
	for (int i = 0; i < K; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int s = 1, e = N / 2;
		while (s <= e) {
			int mid = (s + e) / 2;
			if (x1 <= A[mid].second)
				e = mid - 1;
			else
				s = mid + 1;
		}
		bit.add(s, 1);
	}
	f(f, 1, N / 2 - 1, 0);
	cout << ans1 << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...