#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
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())
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
225 ms |
18592 KB |
Output is correct |
| 2 |
Correct |
212 ms |
18736 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
326 ms |
33840 KB |
Output is correct |
| 2 |
Correct |
289 ms |
27312 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
593 ms |
64020 KB |
Output is correct |
| 2 |
Correct |
545 ms |
40364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1018 ms |
104664 KB |
Output is correct |
| 2 |
Correct |
769 ms |
60808 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
979 ms |
91604 KB |
Output is correct |
| 2 |
Correct |
849 ms |
57416 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
