Submission #1159142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159142		Der_Vlapos	Furniture (JOI20_furniture)	C++20	100 / 100	998 ms	14248 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()

// #define int ll

const int mod1 = 1e9 + 7;
const int mod2 = 998244353;

int dp1[1003][1003];
int dp2[1003][1003];

struct test
{
    void solve()
    {
        int n, m;
        cin >> n >> m;

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cin >> dp1[i][j];

        dp2[n - 1][m - 1] = 1;

        for (int i = n - 1; i >= 0; --i)
            for (int j = m - 1 - (i == n - 1); j >= 0; --j)
                if (!dp1[i][j])
                    dp2[i][j] = max(dp2[i + 1][j], dp2[i][j + 1]);

        dp1[0][0] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = (i == 0); j < m; ++j)
                if (!dp1[i][j])
                    dp1[i][j] = max((i ? dp1[i - 1][j] : 0), (j ? dp1[i][j - 1] : 0));
                else
                    dp1[i][j] = 0;

        vector<vector<int>> good(n, vector<int>(m));
        vector<int> cntG(n + m + 1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
            {
                good[i][j] = (dp1[i][j] and dp2[i][j]);
                cntG[i + j] += good[i][j];
            }

        int q;
        cin >> q;
        queue<pii> bfs;

        vector<int> dx4 = {-1, 1};
        vector<int> dy4 = {1, -1};

        auto isG = [&](int x, int y) -> bool
        {
            return x >= 0 and y >= 0 and x < n and y < m;
        };

        for (int i = 0; i < q; ++i)
        {
            {
                int x, y;
                cin >> x >> y;
                --x, --y;
                if (!good[x][y])
                {
                    cout << "1\n";
                }
                else if (cntG[x + y] == 1)
                {
                    cout << "0\n";
                }
                else
                {
                    cout << "1\n";
                    good[x][y] = 0;
                    bfs.push({x, y});
                }
            }
            while (bfs.size())
            {
                auto [x, y] = bfs.front();
                bfs.pop();
                cntG[x + y]--;
                assert(cntG[x + y]);

                for (int d = 0; d < 2; ++d)
                {
                    int tox = x + dx4[d];
                    int toy = y + dy4[d];
                    if (!isG(tox, toy) or !good[tox][toy])
                    {
                        if (isG(x, toy) and good[x][toy])
                        {
                            good[x][toy] = 0;
                            bfs.push({x, toy});
                        }
                        if (isG(tox, y) and good[tox][y])
                        {
                            good[tox][y] = 0;
                            bfs.push({tox, y});
                        }
                    }
                }
            }
        }
    }
};

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

furniture.cpp:118:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  118 | main()
      | ^~~~

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