#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
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()){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
5872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
7408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
12116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
446 ms |
19048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
452 ms |
18404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
