Submission #237903

#	Time	Username	Problem	Language	Result	Execution time	Memory
237903		MrRobot_28	Plahte (COCI17_plahte)	C++17	160 / 160	1018 ms	104664 KiB

plahte

#include<bits/stdc++.h>
using namespace std;
vector <pair <pair <int, int>, pair <int, int> > > mat;
vector <pair <int, int> > x;
bool cmp(int a, int b)
{
	if(x[a].first == x[b].first)
	{
		return x[a].second < x[b].second;
	}
	return x[a].first < x[b].first;
}
vector <vector <int> > colors;
vector <vector <int> > g;
vector <int> p;
vector <int> ans;
set <int> dfs(int v)
{
	set <int> st;
	set <int> :: iterator it;
	for(int i = 0; i < (int)g[v].size(); i++)
	{
		set <int> st1 = dfs(g[v][i]);
		if(st1.size() > st.size())
		{
			for(it = st.begin(); it != st.end(); it++)
			{
				st1.insert(*it);
			}
			swap(st, st1);
		}
		else
		{
			for(it = st1.begin(); it != st1.end(); it++)
			{
				st.insert(*it);
			}
		}
	}
	for(int i = 0; i < (int)colors[v].size(); i++)
	{
		st.insert(colors[v][i]);
	}
	ans[v] = st.size();
	return st;
}
vector <set <pair <int, int> > > tree;
void updater(int v, int l, int r, int al, int ar, pair <int, int> a)
{
	if(l >= al && r <= ar)
	{
		tree[v].erase(a);
	}
	else if(l <= ar && r >= al)
	{
		updater(v * 2, l, (r + l) / 2, al, ar, a);
		updater(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, a);
	}
}
void updateup(int v, int l, int r, int al, int ar, pair <int, int> a)
{
	if(l >= al && r <= ar)
	{
		tree[v].insert(a);
	}
	else if(l <= ar && r >= al)
	{
		updateup(v * 2, l, (r + l) / 2, al, ar, a);
		updateup(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, a);
	}
}
int fans(int v, int l, int r, int ind, int y)
{
	set <pair <int, int> > :: iterator it;
	it = tree[v].lower_bound({y, 0});
	if(l == r)
	{
		if(it == tree[v].end())
		{
			return -1;
		}
		else
		{
			return it -> second;
		}
	}
	int it1 = -1, it2 = -1;
	if(ind <= (r + l) / 2)
	{
		it1 = fans(v * 2, l, (r + l) / 2, ind, y);
	}
	else
	{
		it1 = fans(v * 2 + 1, (r + l) / 2 + 1, r, ind, y);
	}
	if(it != tree[v].end())
	{
		it2 = it -> second;
	}
	if(it1 == -1)
	{
		return it2;
	}
	else if(it2 == -1)
	{
		return it1;
	}
	else if(mat[it1].second.second < mat[it2].second.second)
	{
		return it1;
	}
	else
	{
		return it2;
	}
}
signed main() {
	int n, m;
	cin >> n >> m;
	ans.resize(n + 1, 0);
	g.resize(n + 1);
	p.resize(n, -1);
	colors.resize(n + 1);
	mat.resize(n);
	vector <pair <pair <int, int>, int> > scan;
	vector <int> uniq;
	for(int i = 0; i < n; i++)
	{
		cin >> mat[i].first.first >> mat[i].first.second >> mat[i].second.first >> mat[i].second.second;
		scan.push_back({{mat[i].first.first, -1}, i});
		scan.push_back({{mat[i].second.first, 1}, i});
		uniq.push_back(mat[i].second.second);
		uniq.push_back(mat[i].first.second);
	}
	x.resize(m);
	vector <int> col(m);
	vector <int> ind(m);
	for(int i = 0; i < m; i++)
	{
		cin >> x[i].first >> x[i].second >> col[i];
		ind[i] = i;
		uniq.push_back(x[i].second);
	}
	sort(uniq.begin(), uniq.end());
	int r = unique(uniq.begin(), uniq.end()) - uniq.begin();
	tree.resize(4 * r);
	sort(ind.begin(), ind.end(), cmp);
	sort(scan.begin(), scan.end());
	int j = 0;
	set <pair <int, int> > st;
	for(int i = 0; i < (int)ind.size(); i++)
	{
		while(j < (int)scan.size() && (scan[j].first.first < x[ind[i]].first || scan[j].first.first== x[ind[i]].first && scan[j].first.second == -1))
		{
			int it = scan[j].second;
			int left = lower_bound(uniq.begin(), uniq.begin() + r, mat[it].first.second) - uniq.begin();
			int right = lower_bound(uniq.begin(), uniq.begin() + r, mat[it].second.second) - uniq.begin();
			if(scan[j].first.second == 1)
			{
				updater(1, 0, r - 1, left, right, {mat[it].second.second, it});
			}
			else
			{
				int it1 = fans(1, 0, r - 1, left, mat[it].second.second);
				if(it1 != -1)
				{
					g[it1].push_back(it);
					p[it] = it1;
				}
				updateup(1, 0, r - 1, left, right, {mat[it].second.second, it});
			}
			j++;
		}
		int e = ind[i];
		int ind1 = lower_bound(uniq.begin(), uniq.begin() + r, x[e].second) - uniq.begin();
		int it1 = fans(1, 0, r - 1, ind1, x[e].second);
		if(it1 != -1)
		{
			colors[it1].push_back(col[e]);
		}
	}
	while(j < scan.size())
	{
		int it = scan[j].second;
			int left = lower_bound(uniq.begin(), uniq.begin() + r, mat[it].first.second) - uniq.begin();
			int right = lower_bound(uniq.begin(), uniq.begin() + r, mat[it].second.second) - uniq.begin();
			if(scan[j].first.second == 1)
			{
				updater(1, 0, r - 1, left, right, {mat[it].second.second, it});
			}
			else
			{
				int it1 = fans(1, 0, r - 1, left, mat[it].second.second);
				if(it1 != -1)
				{
					g[it1].push_back(it);
					p[it] = it1;
				}
				updateup(1, 0, r - 1, left, right, {mat[it].second.second, it});
			}
			j++;
	}
	for(int i = 0; i < n; i++)
	{
		if(p[i] == -1)
		{
			g[n].push_back(i);
		}
	}
	dfs(n);
	for(int i = 0; i < n; i++){
		cout << ans[i] << "\n";
	}
	return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:153:113: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while(j < (int)scan.size() && (scan[j].first.first < x[ind[i]].first || scan[j].first.first== x[ind[i]].first && scan[j].first.second == -1))
plahte.cpp:182:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j < scan.size())
        ~~^~~~~~~~~~~~~

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