Submission #1262400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262400		phtung	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	37 ms	40504 KiB

mushrooms

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long

const int inf = 1e18 + 7;
const int maxn = 5e5 + 5;
int r, c, d, k;
vector<vector<char>> grid;

struct Fenw
{
    vector<vector<int>> tree;
    int n, m;

    Fenw(int n_, int m_)
    {
        n = n_, m = m_;
        tree.resize(n + 5, vector<int>(m + 5, 0));
    }

    void update(int i, int j, int val)
    {
        for(int u = i; u <= n; u += u & -u)
        {
            for(int v = j; v <= m; v += v & -v)
                tree[u][v] += val;
        }
    }

    int preSum(int i, int j)
    {

        int ans = 0;
        for(int u = i; u > 0; u -= u &-u)
        {
            for(int v = j; v > 0; v -= v & -v)
                ans += tree[u][v];
        }
        return ans;
    }

    int query(int i, int j, int u, int v)
    {
        return preSum(u, v) - preSum(i - 1, v) - preSum(u, j - 1) + preSum(i - 1, j - 1);
    }
};

void solve()
{
    cin >> r >> c >> d >> k;
    grid.resize(r + 5, vector<char>(c + 5));

    vector<pair<int,int>> nam, tuoi;

    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            cin >> grid[i][j];

            if(grid[i][j] == 'M') nam.push_back({i, j});

            if(grid[i][j] == 'S') tuoi.push_back({i, j});
        }
    }

    Fenw bit(r, c);

    for(auto [x, y] : tuoi)
    {
        int i, j, u, v;
        i = max(1ll, x - d), j = max(1ll, y - d);
        u = min(r, x + d), v = min(c, y + d);
        bit.update(i, j, 1);
        bit.update(i, v + 1, -1);
        bit.update(u + 1, j, -1);
        bit.update(u + 1, v + 1, 1);
    }

    int res = 0;

    for(auto [x, y] : nam)
    {
        int num = bit.preSum(x, y);
        res += (num >= k);
    }

    cout << res << "\n";


}

signed main()
{


    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t start = clock();

    int t = 1;

    while(t--) solve();

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0;

}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19
• Subtask 6: 21 / 21