Submission #775666

#	Time	Username	Problem	Language	Result	Execution time	Memory
775666		DangerNoodle7591	Paint (COI20_paint)	C++17	9 / 100	43 ms	7384 KiB

paint

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
//#define int long long int
#define N 200005
int limit[N][2],renk[N];
int father[N];
int dsu(int x){
	if(father[x]==x)return x;
	return father[x]=dsu(father[x]);
}
void kardes(int x,int y){
	x=dsu(x),y=dsu(y);
	if(x==y)return;
	father[y]=x;
	limit[x][0]=min(limit[x][0],limit[y][0]);

	limit[x][1]=max(limit[x][1],limit[y][1]);
}
int geldik[N];
int main(){
	lalala;
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			cin>>renk[j];
			limit[j][0]=limit[j][1]=j;
			father[j]=j;
		}
	}
	for(int i=1;i<=m;i++){
		if(geldik[i])continue;
		geldik[i]=1;
		for(int j=i-1;j>0;j--){
			if(renk[j]!=renk[i])break;

			geldik[j]=1;
			kardes(i,j);
		}
		for(int j=i+1;j<=m;j++){
			if(renk[j]!=renk[i])break;
			geldik[j]=1;
			kardes(i,j);
		}
	}
	int q;cin>>q;
	while(q--){
		int x_x,uwu,OwO;cin>>x_x>>uwu>>OwO;
		uwu=dsu(uwu);
		int alt=limit[uwu][0]-1, ust=limit[uwu][1]+1;
		renk[uwu]=OwO;
		if(alt>0&&renk[dsu(alt)]==OwO){
			kardes(uwu,dsu(alt));
		}
		if(ust<=m&&renk[dsu(ust)]==OwO){
			kardes(uwu,dsu(ust));
		}
	}
	for(int i=0;i<n;i++){
		for(int j=1;j<=m;j++){
			cout<<renk[dsu(j)]<<" ";
		}cout<<endl;
	}

	
	
}

• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 31
• Subtask 4: 0 / 52