Submission #1180554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180554		ALTAKEXE	Furniture (JOI20_furniture)	C++20	100 / 100	1252 ms	394324 KiB

furniture

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pii pair<int, int>
#define pb push_back
#define eb emplace_back
#define inf INT_MAX
#define all(x) x.begin(), x.end()
const int MOD = 1e9 + 7;
using namespace std;
vector<vector<int>> R(10002, vector<int>(10002, 1));
vector<int> L(20001, 0);
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            R[i][j] = 0;
            L[i + j]++;
        }
    }
    const auto ok = [&](const int X, const int Y) -> int
    {
        if (R[X][Y] == 1)
        {
            return 1;
        }
        if (L[X + Y] == 1)
        {
            return 0;
        }
        std::stack<std::pair<int, int>> st;
        const auto push = [&](const int x, const int y)
        {
            if (R[x][y] == 0)
            {
                R[x][y] = 1;
                --L[x + y];
                st.emplace(x, y);
            }
        };
        push(X, Y);
        while (!st.empty())
        {
            const int x = st.top().first;
            const int y = st.top().second;
            st.pop();
            if (R[x - 1][y + 1] == 1)
            {
                push(x - 1, y);
                push(x, y + 1);
            }
            if (R[x + 1][y - 1] == 1)
            {
                push(x, y - 1);
                push(x + 1, y);
            }
        }
        return 1;
    };
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            int z;
            cin >> z;
            if (z == 1)
                ok(i, j);
        }
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int xx, yy;
        cin >> xx >> yy;
        cout << ok(xx, yy) << '\n';
    }
}
int main()
{
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

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