Submission #446829

#TimeUsernameProblemLanguageResultExecution timeMemory
446829MOUF_MAHMALATPaint (COI20_paint)C++11
0 / 100
37 ms2116 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() using namespace std; typedef int ll; ll n,m,a[200009],p[200009]; ll l[200009],r[200009],q; ll gp(ll z) { if(p[z]==z) return z; return p[z]=gp(p[z]); } void mrg(ll x,ll y) { x=gp(x),y=gp(y); if(x==y||a[x]!=a[y]) return; if(r[x]-l[x]<r[y]-l[y]) swap(x,y); p[y]=x; l[x]=min(l[x],l[y]); r[x]=max(r[x],r[y]); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; for(ll i=1; i<=m; i++) { cin>>a[i]; p[i]=l[i]=r[i]=i; } for(ll i=1; i<m; i++) mrg(i,i+1); cin>>q; while(q--) { ll x,y; cin>>x>>x>>y; x=gp(x); a[x]=y; if(l[x]>1) mrg(x,l[x]-1); if(r[x]<n) mrg(x,r[x]+1); } for(ll i=1; i<=m; i++) cout<<a[gp(i)]<<" "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...