Submission #516363

#	Time	Username	Problem	Language	Result	Execution time	Memory
516363		Jomnoi	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	68 ms	29636 KiB

mushrooms

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

vector <vector <char>> a;

class Fenwick {
    protected :
        int R, C;
        vector <vector <int>> fenwick;
    public :
        Fenwick(int r, int c) : R(r), C(c) {
            fenwick.resize(r + 10, vector <int> (c + 10, 0));
        } 

        int lsb(int x) {
            return x & -x;
        }

        void update(int x, int y, int val) {
            for(; x <= R; x += lsb(x)) {
                for(int idx = y; idx <= C; idx += lsb(idx)) {
                    fenwick[x][idx] += val;
                }
            }
        }

        int query(int x, int y) {
            int res = 0;
            for(; x > 0; x -= lsb(x)) {
                for(int idx = y; idx > 0; idx -= lsb(idx)) {
                    res += fenwick[x][idx];
                }
            }
            return res;
        }
};

int main() {
    int R, C, D, K;
    scanf(" %d %d %d %d", &R, &C, &D, &K);
    a.resize(R + 10, vector <char> (C + 10));
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            scanf(" %c", &a[i][j]);
        }
    }

    Fenwick fw(R, C);
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            if(a[i][j] == 'S') {
                int min_x = max(1, i - D), max_x = min(R + 1, i + D + 1);
                int min_y = max(1, j - D), max_y = min(C + 1, j + D + 1);
                fw.update(min_x, min_y, 1);
                fw.update(max_x, min_y, -1);
                fw.update(min_x, max_y, -1);
                fw.update(max_x, max_y, 1);
            }
        }
    }

    if(DEBUG) {
        cout << "Debugging :\n";
        for(int i = 1; i <= R; i++) {
            for(int j = 1; j <= C; j++) {
                cout << fw.query(i, j) << " ";
            }
            cout << endl;
        }
    }

    int ans = 0;
    for(int i = 1; i <= R; i++) {
        for(int j = 1; j <= C; j++) {
            if(a[i][j] == 'M' and fw.query(i, j) >= K) {
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf(" %d %d %d %d", &R, &C, &D, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:45:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |             scanf(" %c", &a[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

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