oj.uz

답안 #236890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236890 2020-06-03T17:14:03 Z DanShaders Plahte (COCI17_plahte) C++17
160 / 160
 554 ms 62456 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) begin(x), end(x)
#define x first
#define y second
typedef long long ll;
typedef long double ld;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;

const int MAX_N = 1 << 18, MAX_TREE = 1 << 19, MAX_M = 8e4 + 10, INF = 0x3f3f3f3f;

struct Event {
	char type; // 0 - open, 1 - shoot, 2 - close
	int x, y0, y1, id;
};

vector<Event> events;

bool operator<(const Event &a, const Event &b) {
	if (a.x < b.x)
		return 1;
	if (a.x > b.x)
		return 0;
	if (a.type < b.type)
		return 1;
	if (a.type > b.type)
		return 0;
	return 0;
}

vector<pair<int, int>> tree1[MAX_TREE];

void addRect(const Event &e) {
	int y0 = e.y0 + MAX_N;
	int y1 = e.y1 + MAX_N;
	while (y0 <= y1) {
		if (y0 & 1)	tree1[y0].push_back({e.x, e.id});
		if (!(y1 & 1))	tree1[y1].push_back({e.x, e.id});
		y0 = (y0 + 1) / 2;
		y1 = (y1 - 1) / 2;
	}
}

void removeRect(const Event &e) {
	int y0 = e.y0 + MAX_N;
	int y1 = e.y1 + MAX_N;
	while (y0 <= y1) {
		if ((y0 & 1) && tree1[y0].size())	{
			assert(tree1[y0].back().y == e.id);
			tree1[y0].pop_back();
		}
		if (!(y1 & 1) && tree1[y1].size()) {
			assert(tree1[y1].back().y == e.id);
			tree1[y1].pop_back();
		}
		y0 = (y0 + 1) / 2;
		y1 = (y1 - 1) / 2;
	}
}

int getOwner(const Event &e) {
	int i = e.y0 + MAX_N;
	pair<int, int> res{-INF, 0};
	while (i) {
		if (tree1[i].size() && tree1[i].back() > res)
			res = tree1[i].back();
		i /= 2;
	}
	return res.y;
}

vector<int> childrens[MAX_M];
set<int> owned[MAX_M];
int ans[MAX_N];

set<int> *dfs(int u) {
	vector<pair<int, set<int>*>> cs;
	for (int v : childrens[u]) {
		auto res = dfs(v);
		cs.push_back({res->size(), res});
	}
	if (cs.size() == 0) {
		ans[u] = (int) owned[u].size();
		return &owned[u];
	}
	set<int> *v = max_element(all(cs))->y;
	for (auto p : cs) {
		if (p.y != v)
			v->insert(p.y->begin(), p.y->end());
	}
	v->insert(all(owned[u]));
	ans[u] = (int) v->size();
	return v;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	map<int, int> yremap;
	for (int i = 0; i < n; ++i) {
		int x0, y0, x1, y1;
		cin >> x0 >> y0 >> x1 >> y1;
		events.push_back({0, x0, y0, y1, i + 1});
		events.push_back({2, x1, y0, y1, i + 1});
		yremap[y0] = yremap[y1] = 0;
	}
	for (int i = 0; i < m; ++i) {
		int x, y, k;
		cin >> x >> y >> k;
		events.push_back({1, x, y, y, k});
		yremap[y] = 0;
	}
	int cnt = 0;
	for (auto &p : yremap)
		p.y = cnt++;
	assert(cnt < MAX_N);
	for (auto &e : events)
		e.y0 = yremap[e.y0], e.y1 = yremap[e.y1];
	sort(all(events));
	for (auto e : events) {
		if (e.type == 0) {
			childrens[getOwner(e)].push_back(e.id);
			addRect(e);
		} else if (e.type == 1) {
			owned[getOwner(e)].insert(e.id);
		} else if (e.type == 2) {
			removeRect(e);
		}
	}
	dfs(0);
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << "\n";
	return 0;
}

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 142 ms 29444 KB Output is correct
2 Correct 135 ms 29572 KB Output is correct
3 Correct 16 ms 18304 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 166 ms 33644 KB Output is correct
2 Correct 173 ms 31876 KB Output is correct
3 Correct 15 ms 18304 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 45816 KB Output is correct
2 Correct 294 ms 39400 KB Output is correct
3 Correct 15 ms 18304 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 548 ms 62456 KB Output is correct
2 Correct 546 ms 52944 KB Output is correct
3 Correct 15 ms 18304 KB Output is correct

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 554 ms 59476 KB Output is correct
2 Correct 477 ms 50560 KB Output is correct
3 Correct 15 ms 18304 KB Output is correct