#include<bits/stdc++.h>
using namespace std;
map<int,int>cc,c2;
map<int,tuple<vector<int>,vector<int>,vector<int>>>mp;
struct ST{
int a,b,c,d,p;
}q[80100];
int v[1<<20],lz[1<<20],cnt,n,m,ans[80100];
void pd(int i,bool b){
if(~lz[i]){
v[i]=lz[i];
if(b)
lz[i*2+1]=lz[i*2]=lz[i];
lz[i]=-1;
}
}
int query(int i,int l,int r,int x){
pd(i,l-r);
if(l==r)return v[i];
if(l+r>>1>=x)
return query(i*2,l,l+r>>1,x);
return query(i*2+1,l+r+2>>1,r,x);
}
void upd(int i,int l,int r,int tl, int tr,int x){
pd(i,l-r);
if(tl<=l&&r<=tr)
return lz[i]=x,pd(i,l-r);
if(l>tr||tl>r) return;
upd(i*2,l,l+r>>1,tl,tr,x);
upd(i*2+1,l+r+2>>1,r,tl,tr,x);
}
void merge(set<int>&a,set<int>b){
if(a.size()<b.size())
swap(a,b);
for(auto i:b)
a.insert(i);
b.clear();
}
pair<int,int>pb[80100];
vector<int>given[80100],adj[80100];
set<int> dfs(int n){
set<int>colors;
for(auto i:given[n])
colors.insert(i);
for(auto i:adj[n])
merge(colors,dfs(i));
ans[n]=colors.size();
return colors;
}
int main(){
memset(lz,-1,sizeof lz);
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>q[i].a>>q[i].b>>q[i].c>>q[i].d;
cc[q[i].b],cc[q[i].d];
get<0>(mp[q[i].a]).push_back(i);
get<1>(mp[q[i].c]).push_back(i);
}
for(int i=1,a,b,c;i<=m;i++){
cin>>a>>b>>c;
get<2>(mp[a]).push_back(i);
c2[c];pb[i]={b,c};
cc[b];
}
for(auto&[i,j]:c2)
j=++cnt;cnt=0;
for(auto&[i,j]:cc)
j=++cnt;
for(auto[xx,ab]:mp){
for(auto i:get<0>(ab))
q[i].p=query(1,1,cnt,cc[q[i].b]),upd(1,1,cnt,cc[q[i].b],cc[q[i].d],i);
for(auto i:get<2>(ab))
given[query(1,1,cnt,cc[pb[i].first])].push_back(c2[pb[i].second]);
for(auto i:get<1>(ab))
upd(1,1,cnt,cc[q[i].b],cc[q[i].d],q[i].p);
}
for(int i=1;i<=n;i++)
adj[q[i].p].push_back(i);
dfs(0);
for(int i=1;i<=n;i++)
cout<<ans[i]<<'\n';
}
Compilation message
plahte.cpp: In function 'int query(int, int, int, int)':
plahte.cpp:20:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | if(l+r>>1>=x)
| ~^~
plahte.cpp:21:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | return query(i*2,l,l+r>>1,x);
| ~^~
plahte.cpp:22:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | return query(i*2+1,l+r+2>>1,r,x);
| ~~~^~
plahte.cpp: In function 'void upd(int, int, int, int, int, int)':
plahte.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | upd(i*2,l,l+r>>1,tl,tr,x);
| ~^~
plahte.cpp:30:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | upd(i*2+1,l+r+2>>1,r,tl,tr,x);
| ~~~^~
plahte.cpp: In function 'int main()':
plahte.cpp:66:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
66 | for(auto&[i,j]:c2)
| ^~~
plahte.cpp:67:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
67 | j=++cnt;cnt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
29532 KB |
Output is correct |
| 2 |
Correct |
172 ms |
28500 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
34900 KB |
Output is correct |
| 2 |
Correct |
201 ms |
33076 KB |
Output is correct |
| 3 |
Correct |
3 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
375 ms |
54180 KB |
Output is correct |
| 2 |
Correct |
417 ms |
45056 KB |
Output is correct |
| 3 |
Correct |
3 ms |
10840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
716 ms |
76444 KB |
Output is correct |
| 2 |
Correct |
753 ms |
67660 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
649 ms |
75088 KB |
Output is correct |
| 2 |
Correct |
685 ms |
63988 KB |
Output is correct |
| 3 |
Correct |
3 ms |
10848 KB |
Output is correct |
