oj.uz

Submission #715462

# Submission time Handle Problem Language Result Execution time Memory
715462 2023-03-26T21:20:24 Z mbfibat Plahte (COCI17_plahte) C++17
160 / 160
 795 ms 210880 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]);
	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();
//			cerr << cur_event.x << ' ' << cur_event.y1 << ' ' << cur_event.y2 << ' ' << cur_event.t << ' ' << cur_event.id << '\n';
			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());
//				cerr << "CUU: " << id << ' ' << par[id] << '\n';
				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);
//				cerr << "QUERY: " << cur_seg << '\n';
				col[cur_seg].insert(cur_event.id);							
				s.erase(s.begin());
			}
		}
	}	

	/*	
	cerr << "GRAPH\n";
	for (int i = 1; i <= n; i++) {
		cerr << '!' << i << '\n';
		for (int v : adj[i]) cerr << v << ' ';
		cerr << '\n';
	}

	cerr << "COL\n";
	for (int i = 1; i <= n; i++) {
		cerr << '!' << i << '\n';
		for (int v : col[i]) cerr << v << ' ';
		cerr << '\n';
	}
	*/
	

	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 227 ms 83488 KB Output is correct
2 Correct 238 ms 83744 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 86824 KB Output is correct
2 Correct 246 ms 88132 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 456 ms 139436 KB Output is correct
2 Correct 438 ms 133128 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 795 ms 210880 KB Output is correct
2 Correct 752 ms 192008 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 750 ms 207708 KB Output is correct
2 Correct 704 ms 198972 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct