Submission #403981

#	Time	Username	Problem	Language	Result	Execution time	Memory
403981		penguinhacker	Plahte (COCI17_plahte)	C++14	160 / 160	433 ms	57852 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 (maybe segtree tbh) 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;
vector<int> d, s[3*4*mxN], adj[mxN];
set<int> dp[mxN];

void upd(int ql, int qr, int x, int u=1, int l=0, int r=d.size()-1) {
	if (l>qr||r<ql)
		return;
	if (ql<=l&&r<=qr) {
		x^-1?s[u].push_back(x):s[u].pop_back();
		return;
	}
	int mid=(l+r)/2;
	upd(ql, qr, x, 2*u, l, mid);
	upd(ql, qr, x, 2*u+1, mid+1, r);
}

int qry(int x, int u=1, int l=0, int r=d.size()-1) {
	int cur=s[u].empty()?-1:s[u].back();
	if (l==r)
		return cur;
	int mid=(l+r)/2;
	int lo=x<=mid?qry(x, 2*u, l, mid):qry(x, 2*u+1, mid+1, r);
	return lo^-1?lo:cur;
}

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];
		d.push_back(ys[i][0]);
		d.push_back(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];
		d.push_back(ball[i][0]);
		e.push_back({x, 2, i});
	}
	sort(d.begin(), d.end());
	d.resize(unique(d.begin(), d.end())-d.begin());
	for (int i=0; i<n; ++i) {
		ys[i][0]=lower_bound(d.begin(), d.end(), ys[i][0])-d.begin();
		ys[i][1]=lower_bound(d.begin(), d.end(), ys[i][1])-d.begin();
	}
	for (int i=0; i<m; ++i)
		ball[i][0]=lower_bound(d.begin(), d.end(), ball[i][0])-d.begin();
	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=qry(ys[i][0]);
			if (x^-1) {
				p[i]=x;
				adj[p[i]].push_back(i);
			}
			upd(ys[i][0], ys[i][1], i);
		} else if (a[1]==2) {
			int x=qry(ball[i][0]);
			if (x^-1)
				dp[x].insert(ball[i][1]);
		} else {
			upd(ys[i][0], ys[i][1], -1);
		}
	}
	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: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32