CF 631B 题解

注意到每次只染色一行或者一列，那么我们最后输出第i行第j列的数字是多少的时候只需要看一下最后一次i行和第j行被染了什么颜色，所以我们需要对每一行和一列记录最后一次染色的颜色。

但是我们也需要比较是行比列后染色还是列比行后染色，所以我们还需要记录一下每行每列染色的最后时间。

然后模拟即可

#include <cstdio>

#include <iostream>

using namespace std;

int x[],y[],z[];

int line[],cnt1,row[],cnt2;

int bo1[],bo2[];

int a[][];

int main() {

    freopen("matrix.in","r",stdin);

    freopen("matrix.out","w",stdout);

    int n,m,q;

    scanf("%d%d%d",&n,&m,&q);

    for(register int i=;i<=q;i++){

        scanf("%d%d%d",&x[i],&y[i],&z[i]);

    }

    for(register int i=q;i>=;i--){

        if(x[i]==){

            if(bo2[y[i]]==){

                row[++cnt2]=i;

                bo2[y[i]]=;

            }

        }

        if(x[i]==){

            if(bo1[y[i]]==){

                line[++cnt1]=i;

                bo1[y[i]]=;

            }

        }

    }

    register int l1=cnt1,l2=cnt2;

    while(l1>&&l2>){

        if(row[l2]<line[l1]){

            for(register int j=;j<=m;j++){

                a[y[row[l2]]][j]=z[row[l2]];

            }

            --l2;

        }

        else{

            for(register int j=;j<=n;j++){

                a[j][y[line[l1]]]=z[line[l1]];

            }

            --l1;

        }

    }

    while(l1>){

        for(register int j=;j<=n;j++){

            a[j][y[line[l1]]]=z[line[l1]];

        }

        --l1;

    }

    while(l2>){

        for(register int j=;j<=m;j++){

            a[y[row[l2]]][j]=z[row[l2]];

        }

        --l2;

    }

    for(register int i=;i<=n;i++){

        for(register int j=;j<=m;j++){

            printf("%d ",a[i][j]);

        }

        printf("\n");

    }

    return ;

}

/*

3 3 3

1 1 3

2 2 1

1 2 2

5 3 5

1 1 1

1 3 1

1 5 1

2 1 1

2 3 1

6 4 9

1 1 1

1 3 2

1 4 3

2 2 4

1 2 5

2 3 6

1 4 7

2 2 1

1 2 1

*/

巴特西

CF 631B 题解

最新文章

热门文章