Submission #473503

#	Time	Username	Problem	Language	Result	Execution time	Memory
473503		blue	Furniture (JOI20_furniture)	C++17	100 / 100	2357 ms	15972 KiB

furniture

#include <iostream>
#include <vector>
using namespace std;

const int MX = 1'000;

int N, M;
vector< vector<int> > C(1+MX+1, vector<int>(1+MX+1, 1));

vector<int> ct(1+3*MX, 0);
vector<int> sz(1+3*MX, 0);

void fwd(int x, int y)
{
    // cerr << "fwd " << x << ' ' << y << '\n';
    if(x+1 <= N && C[x+1][y-1] && !C[x+1][y])
    {
        ct[x+y+1]++;
        C[x+1][y] = 1;
        fwd(x+1, y);
    }
    // cerr << (y+1 <= M) << ' ' << C[x-1][y+1] << ' ' << !C[x][y+1] << '\n';
    if(y+1 <= M && C[x-1][y+1] && !C[x][y+1])
    {
        ct[x+y+1]++;
        C[x][y+1] = 1;
        fwd(x, y+1);
    }
}



void bwd(int x, int y)
{
    if(1 <= x-1 && C[x-1][y+1] && !C[x-1][y])
    {
        ct[x+y-1]++;
        C[x-1][y] = 1;
        bwd(x-1, y);
    }

    if(1 <= y-1 && C[x+1][y-1] && !C[x][y-1])
    {
        ct[x+y-1]++;
        C[x][y-1] = 1;
        bwd(x, y-1);
    }
}




int main()
{
    cin >> N >> M;

    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
        {
            cin >> C[i][j];
            if(C[i][j]) ct[i+j]++;
            sz[i+j]++;
        }
    }

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(C[i][j])
            {
                fwd(i, j);
                bwd(i, j);
            }

    // cerr << ct[1+1] << '\n';
    //
    // cerr << "init:\n";
    // for(int i = 0; i <= N+1; i++)
    // {
    //     for(int j = 0; j <= M+1; j++)
    //     {
    //         cerr << C[i][j] << ' ';
    //     }
    //     cerr << '\n';
    // }
    // cerr << "\n\n";


    int Q;
    cin >> Q;
    for(int q = 1; q <= Q; q++)
    {
        int X, Y;
        cin >> X >> Y;

        // cerr << ct[X+Y] + 1 << ' ' << sz[X+Y] << '\n';

        if(C[X][Y] == 1)
        {
            cout << "1\n";
        }
        else if(ct[X+Y] + 1 == sz[X+Y])
        {
            cout << "0\n";
            continue;
        }
        else
        {
            cout << "1\n";
            C[X][Y] = 1;
            ct[X+Y]++;
            fwd(X, Y);
            bwd(X, Y);
        }

        // cerr << "after update: ";
        // for(int i = 0; i <= N+1; i++)
        // {
        //     for(int j = 0; j <= M+1; j++)
        //     {
        //         cerr << C[i][j] << ' ';
        //     }
        //     cerr << '\n';
        // }
        // cerr << "\n\n";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95