Submission #237893

#	Time	Username	Problem	Language	Result	Execution time	Memory
237893		MrRobot_28	Plahte (COCI17_plahte)	C++17	0 / 160	452 ms	19048 KiB

plahte

#include<bits/stdc++.h>
using namespace std;
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 < 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 < colors[v].size(); i++)
	{
		st.insert(colors[v][i]);
	}
	ans[v] = st.size();
	return st;
}
signed main() {
	int n, m;
	cin >> n >> m;
	ans.resize(n, 0);
	g.resize(n + 1);
	p.resize(n, -1);
	colors.resize(n + 1);
	vector <pair <pair <int, int>, pair <int, int> > > mat(n);
	vector <pair <pair <int, int>, int> > scan;
	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});
	}
	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;
	}
	sort(ind.begin(), ind.end(), cmp);
	sort(scan.begin(), scan.end());
	int j = 0;
	set <pair <int, int> > st;
	for(int i = 0; i < ind.size(); i++)
	{
		while(j < 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;
			if(scan[j].first.second == 1)
			{
				st.erase({mat[it].second.second, it});
			}
			else
			{
				set <pair <int, int> > :: iterator it1;
				it1 = st.lower_bound({mat[it].second.second, 0});
				if(it1 != st.end() && mat[it1 ->second].first.second <= mat[it].first.second)
				{
					p[it] = it1 -> second;
					g[it1 -> second].push_back(it);
				}
				st.insert({mat[it].second.second, it});
			}
			j++;
		}
		set <pair<int, int> > :: iterator it;
		it = st.lower_bound({x[ind[i]].second, 0});
		if(it != st.end() && mat[it -> second].first.second <= x[ind[i]].second)
		{
			colors[it -> second].push_back(col[ind[i]]);
		}
	}
	while(j < scan.size()){
		int it = scan[j].second;
			if(scan[j].first.second == 1)
			{
				st.erase({mat[it].second.second, it});
			}
			else
			{
				set <pair <int, int> > :: iterator it1;
				it1 = st.lower_bound({mat[it].second.second, 0});
				if(it1 != st.end() && mat[it1 ->second].first.second <= mat[it].first.second)
				{
					p[it] = it1 -> second;
					g[it1 -> second].push_back(it);
				}
				st.insert({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 'std::set<int> dfs(int)':
plahte.cpp:20:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~
plahte.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < colors[v].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:73:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ind.size(); i++)
                 ~~^~~~~~~~~~~~
plahte.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < 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:75:108: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   while(j < 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:102:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(j < scan.size()){
        ~~^~~~~~~~~~~~~

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