Submission #1004318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004318		vjudge1	Paint (COI20_paint)	C++17	0 / 100	41 ms	2128 KiB

paint

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int mi[N], mx[N], par[N], color[N];

int root(int x)
{
  if(par[x] == x) return x;
  return par[x] = root(par[x]);
}

void merge(int a, int b)
{
  a = root(a), b = root(b);
  if(a == b) return;
  
  par[a] = b;
  mi[b] = min(mi[a], mi[b]);
  mx[b] = max(mx[a], mx[b]);
}

int main()
{
  int r, c;
  cin >> r >> c;

  for(int i = 0; i < c; i ++)
    mx[i] = mi[i] = par[i] = i;
  
  int a[r][c];

  for(int i = 0; i < r; i ++)
    for(int j = 0; j < c; j ++)
      {
	cin >> a[i][j];
	color[j] = a[i][j];
      }

  int q;
  cin >> q;
  while(q--)
    {
      int i, j, col;
      cin >> i >> j >> col;
      j--;
      i = root(j);

      color[i] = col;
      if(mx[i] + 1 < c && color[root(mx[i] + 1)] == col)
	merge(i, mx[i] + 1);

      if(mi[i] > 0 && color[root(mi[i] - 1)] == col)
	merge(i, mi[i] - 1);
    }

  for(int i = 0; i < c; i ++)
    cout << color[root(i)] << ' ';
  cout << endl;
  return 0;
}

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