Submission #146969

#	Time	Username	Problem	Language	Result	Execution time	Memory
146969		jun6873	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	226 ms	32888 KiB

mushrooms

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

const int maxn = 1<<19;
int h, w, d, k, qn;
string s[500004];

struct query {
    query() {}
    query(int x, int y) : t(2), x(x), y(y) {}
    query(int x, int y1, int y2, int d) : t(1), x(x), y1(y1), y2(y2), d(d) {}
    int t, x, y1, y2, y, d;
} q[1000004];

struct segt {
    int t[maxn*2];
    int merge(int a, int b) { return a+b; }
    void update(int s, int e, int x, int p, int v) {
        if (s==e) t[x] += v;
        else {
            int m = (s+e)/2;
            if (p<=m) update(s, m, 2*x, p, v);
            else update(m+1, e, 2*x+1, p, v);
            t[x] = merge(t[2*x], t[2*x+1]);
        }
    }
    void update(int p, int v) { return update(0, maxn-1, 1, p, v); }
    int query(int s, int e, int x, int l, int r) {
        if (l<=s and e<=r) return t[x];
        else if (l<=e and s<=r) {
            int m = (s+e)/2;
            return merge(query(s, m, 2*x, l, r), query(m+1, e, 2*x+1, l, r));
        } else return 0;
    }
    int query(int l, int r) { return query(0, maxn-1, 1, l, r); }

    void range_update(int l, int r, int v) {
        update(l, v);
        update(r+1, -v);
    }

    int point_query(int p) {
        return query(0, p);
    }
} t;
int main() {
    cin >> h >> w >> d >> k;

    for (int i=0; i<h; i++) cin >> s[i];

    for (int y=0; y<h; y++) for (int x=0; x<w; x++) {
        if (s[y][x] == 'S') {
            int x1 = max(0, x-d), x2 = min(w-1, x+d), y1 = max(0, y-d), y2 = min(h-1, y+d);
            q[qn++] = query(x1, y1, y2, 1);
            q[qn++] = query(x2+1, y1, y2, -1);
        }
        if (s[y][x] == 'M') {
            q[qn++] = query(x, y);
        }
    }

    sort(q, q+qn, [](query x, query y) { return x.x < y.x or (x.x == y.x and x.t < y.t); });

    int ans = 0;
    for (int i=0; i<qn; i++) {
        if (q[i].t == 1) {
            int y1 = q[i].y1, y2 = q[i].y2, d = q[i].d;
            t.range_update(y1, y2, d);
        }

        if (q[i].t == 2) {
            int y = q[i].y;
            ans += t.point_query(y) >= k;
        }
    }

    cout << ans << '\n';
}

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