Submission #862431

#	Time	Username	Problem	Language	Result	Execution time	Memory
862431		Irate	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	68 ms	56180 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
struct SegmentTree{
    vector<int>sTree;
    vector<int>lazy;
    
    void Propagate(int node, int l, int r){
        if(!lazy[node])return;
        sTree[node] += lazy[node];
        if(l != r){
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void R_Update(int node, int l, int r, int ql, int qr, int val){
        Propagate(node, l, r);
        if(ql <= l && r <= qr){
            lazy[node] += val;
            Propagate(node, l, r);
            return;
        }
        if(ql > r || l > qr)return;
        int mid = (l + r) >> 1;
        R_Update(node * 2, l, mid, ql, qr, val);
        R_Update(node * 2 + 1, mid + 1, r, ql, qr, val);
        sTree[node] = sTree[node * 2] + sTree[node * 2 + 1];
    }
    int Query(int node, int l, int r, int pos){
        Propagate(node, l, r);
        if(l == r)return sTree[node];
        int mid = (l + r) >> 1;
        if(pos <= mid){
            return Query(node * 2, l, mid, pos);
        }
        return Query(node * 2 + 1, mid + 1, r, pos);
    }
};
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, d, k;
    cin >> n >> m >> d >> k;
    vector<vector<char>>grid(n + 1, vector<char>(m + 1));
    SegmentTree tree[m + 1];
    for(int i = 0;i <= m;++i){
        tree[i].sTree.resize(4 * n);
        tree[i].lazy.resize(4 * n);
    }
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            cin >> grid[i][j];
            if(grid[i][j] == 'S'){
                int x = max(i - d, 1);
                int y = max(j - d, 1);
                int x_end = min(i + d, n);
                int y_end = min(j + d, m);
                tree[y].R_Update(1, 1, n, x, x_end, 1);
                if(y_end + 1 <= m)tree[y_end + 1].R_Update(1, 1, n, x, x_end, -1);
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n;++i){
        int sum = 0;
        for(int j = 1;j <= m;++j){
            sum += tree[j].Query(1, 1, n, i);
            if(grid[i][j] == 'M' && sum >= k){
                res++;
            }
        }
    }
    cout << res;
}

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