Submission #403858

#	Time	Username	Problem	Language	Result	Execution time	Memory
403858		penguinhacker	Plahte (COCI17_plahte)	C++14	0 / 160	298 ms	34748 KiB

plahte

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

// just build a tree on the rectanges, and then a simple dfs to push the colors down
// the question is how do we build the tree, and how do we find the topmost rectangle that each shot hits
// idea: sweepline
// specifics: put all active rectangles in a set and sweep

const int mxN=80000;
int n, m, p[mxN], ans[mxN];
ar<int, 2> ys[mxN], ball[mxN];
vector<ar<int, 3>> e;
set<ar<int, 3>> s, s2;
vector<int> adj[mxN];
set<int> dp[mxN];

int check(int y) {
	auto it=s.upper_bound({y});
	if (it==s.begin())
		return -1;
	ar<int, 3> a=*(--it);
	if (y<=a[1])
		return a[2];
	it=s2.lower_bound({y});
	if (it==s.end())
		return -1;
	a=*it;
	return y>=a[1]?a[2]:-1;
}

void dfs(int u) {
	for (int v : adj[u]) {
		dfs(v);
		if (dp[v].size()>dp[u].size())
			swap(dp[u], dp[v]);
		for (const int& i : dp[v])
			dp[u].insert(i);
		set<int>().swap(dp[v]);
	}
	ans[u]=dp[u].size();
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<n; ++i) {
		int a, b;
		cin >> a >> ys[i][0] >> b >> ys[i][1];
		e.push_back({a, 1, i});
		e.push_back({b, 3, i});
	}
	for (int i=0; i<m; ++i) {
		int x;
		cin >> x >> ball[i][0] >> ball[i][1];
		e.push_back({x, 2, i});
	}
	sort(e.begin(), e.end());
	memset(p, -1, sizeof(p));
	for (ar<int, 3> a : e) {
		int i=a[2];
		if (a[1]==1) {
			int x=check(ys[i][0]);
			if (x^-1) {
				p[i]=x;
				adj[p[i]].push_back(i);
			}
			s.insert({ys[i][0], ys[i][1], i});
			s2.insert({ys[i][1], ys[i][0], i});
		} else if (a[1]==2) {
			int x=check(ball[i][0]);
			if (x^-1)
				dp[x].insert(ball[i][1]);
		} else {
			s.erase({ys[i][0], ys[i][1], i});
			s2.erase({ys[i][1], ys[i][0], i});
		}
	}
	for (int i=0; i<n; ++i)
		if (p[i]==-1)
			dfs(i);
	for (int i=0; i<n; ++i)
		cout << ans[i] << "\n";
	return 0;
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32