oj.uz

Submission #715463

# Submission time Handle Problem Language Result Execution time Memory
715463 2023-03-26T21:21:32 Z mbfibat Plahte (COCI17_plahte) C++17
160 / 160
 765 ms 209632 KB 
#include <bits/stdc++.h>

using namespace std;

struct Node {
	int lazy = -1, v = 0;
	Node *l = nullptr, *r = nullptr;

	Node(){}
};

Node* root = new Node();

Node*& left(Node* node) {
	if (!node -> l) node -> l = new Node();
	return node -> l;
}

Node*& right(Node* node) {
	if (!node -> r) node -> r = new Node();
	return node -> r;
}

void diffuse(Node* node, int l, int r) {
	if (node -> lazy != -1) {
		node -> v = node -> lazy;
		if (l != r) {
			left(node) -> lazy = node -> lazy; 
			right(node) -> lazy = node -> lazy;
		}
		node -> lazy = -1;
	}
}

void update(Node* node, int l, int r, int L, int R, int v) {
	diffuse(node, l, r);
	if (r < L || R < l) return;
	if (L <= l && r <= R) {
		node -> lazy = v;
		diffuse(node, l, r);
		return;
	}

	int mi = (l + r) / 2;
	update(left(node), l, mi, L, R, v);
	update(right(node), mi + 1, r, L, R, v);
	// Doesn't need to change because always query point
} 

int query(Node* node, int l, int r, int p) {
	diffuse(node, l, r);
	if (p < l || r < p) return 0;
	if (l == r) return node -> v;

	int mi = (l + r) / 2;
	int a = query(left(node), l, mi, p);
	int b = query(right(node), mi + 1, r, p);
	return max(a, b);
}

struct Event {
	int x, y1, y2, t, id;
	Event(){}
	Event(int x, int y1, int y2, int t, int id) : x(x), y1(y1), y2(y2), t(t), id(id) {}
};


int A[100001], B[100001], C[100001], D[100001];

int par[100001];
set<int> col[100001];
vector<int> adj[100001];

int tot[100001];
void dfs(int u, int p) {
	for (int v : adj[u])
		dfs(v, u);
	tot[u] = col[u].size();

	if (col[u].size() > col[p].size()) swap(col[u], col[p]); // small to large
	while (!col[u].empty()) {
		col[p].insert(*col[u].begin());
		col[u].erase(col[u].begin());
	}
}

int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m;

	auto cmp = [](const Event& a, const Event& b) -> bool {
		return a.x < b.x || (a.x == b.x && a.t < b.t) || (a.x == b.x && a.t == b.t && a.y1 < b.y1);
	};
	set<Event, decltype(cmp)> s(cmp);

	for (int i = 1; i <= n; i++) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		s.insert(Event(A[i], B[i], D[i], 1, i));
	}
	for (int i = 1; i <= m; i++) {
		int x, y, c; cin >> x >> y >> c;
		s.insert(Event(x, y, y, 2, c));
	}

	while(!s.empty()) {
		int cur_x = (*s.begin()).x;
		while (!s.empty() && (*s.begin()).x == cur_x) {
			Event cur_event = *s.begin();
			if (cur_event.t == 0) { // revert segment
				update(root, 1, 1000000000, cur_event.y1, cur_event.y2, cur_event.id);				
				s.erase(s.begin());
			}
			else if (cur_event.t == 1) { // add current segment
				int id = cur_event.id;
				par[id] = query(root, 1, 1000000000, cur_event.y1);
				update(root, 1, 1000000000, cur_event.y1, cur_event.y2, cur_event.id);
				adj[par[id]].push_back(id);

				s.erase(s.begin());
				s.insert(Event(C[id] + 1, B[id], D[id], 0, par[id]));
			} else if (cur_event.t == 2) { // add ball to current segment 
				int cur_seg = query(root, 1, 1000000000, cur_event.y1);
				col[cur_seg].insert(cur_event.id);							
				s.erase(s.begin());
			}
		}
	}	

	for (int i = 1; i <= n; i++)
		if (!par[i])
			dfs(i, 0);
	for (int i = 1; i <= n; i++) cout << tot[i] << '\n';
	return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 83396 KB Output is correct
2 Correct 259 ms 83832 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 86696 KB Output is correct
2 Correct 345 ms 88140 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 139244 KB Output is correct
2 Correct 437 ms 133052 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 209632 KB Output is correct
2 Correct 692 ms 190364 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 206404 KB Output is correct
2 Correct 684 ms 197284 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct