#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
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(unordered_set<int>&a,unordered_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];
unordered_set<int> dfs(int n){
unordered_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:21:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | if(l+r>>1>=x)
| ~^~
plahte.cpp:22:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | return query(i*2,l,l+r>>1,x);
| ~^~
plahte.cpp:23:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | 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:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | upd(i*2,l,l+r>>1,tl,tr,x);
| ~^~
plahte.cpp:31:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | upd(i*2+1,l+r+2>>1,r,tl,tr,x);
| ~~~^~
plahte.cpp: In function 'int main()':
plahte.cpp:67:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
67 | for(auto&[i,j]:c2)
| ^~~
plahte.cpp:68:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
68 | j=++cnt;cnt=0;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
148 ms |
29492 KB |
Output is correct |
| 2 |
Correct |
138 ms |
28504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10844 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
162 ms |
35376 KB |
Output is correct |
| 2 |
Correct |
183 ms |
33236 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10840 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
325 ms |
55128 KB |
Output is correct |
| 2 |
Correct |
345 ms |
45376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10840 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
629 ms |
77256 KB |
Output is correct |
| 2 |
Correct |
648 ms |
67668 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10844 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
607 ms |
75756 KB |
Output is correct |
| 2 |
Correct |
631 ms |
64072 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10840 KB |
Output is correct |
