Submission #549047

#	Time	Username	Problem	Language	Result	Execution time	Memory
549047		Belgutei	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	96 ms	22240 KiB

mushrooms

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef BE_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

int n,m,d,e;
string s[500005];
int l,r;
int ans;
int type;

int level,zereg[30];
vector<int> v[30];

void build_tree(){
    zereg[0] = 1;
    for(int i = 0; i < 30; i++){
        if(zereg[i] >= m){
            level = i;
            debug(level);
            break;
        }
        zereg[i+1] = zereg[i] * 2;
    }
    for(int i = 0; i <= level; i++){
        for(int j = 0; j < zereg[i]; j++){
            v[i].pb(0);
        }
    }
}

void dfs(int k, int x){
    int y = zereg[level-k] * x;
    int z = zereg[level-k] * (x + 1) - 1;
    if(l <= y && z <= r){
        v[k][x] += type;
        return;
    }
    if(z<l || y>r || k==level) return;
    v[k+1][x*2] += v[k][x];
    v[k+1][x*2+1] += v[k][x];
    v[k][x] = 0;
    dfs(k+1,x*2);
    dfs(k+1,x*2+1);
}

int go(int pos){
    int ret = 0;
    for(int i = level; i >= 0; i--){
        ret += v[i][pos];
        pos /= 2;
    }
    return ret;
}

int main(){
    IOS
    cin >> n >> m >> d >> e; // distance / minimum number 
    for(int i=0; i<n; i++){
        cin >> s[i];
    }
    build_tree();
    for(int i = 0; i <= min(d,n-1); i++){
        for(int j = 0; j < m; j++){
            if(s[i][j] == 'S'){
                l = max(0,j - d);
                r = min(m-1, j + d);
                type = 1;
                dfs(0,0);
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s[i][j] == 'M'){
                int cnt = go(j);
                if(cnt >= e){
                    ans++;
                }
            }
        }
        if(i-d >= 0){
            for(int j = 0; j < m; j++){
                if(s[i-d][j] == 'S'){
                    l = max(0,j - d);
                    r = min(m-1, j + d);
                    type = -1;
                    dfs(0,0);
                }
            }
        }
        if(i + d + 1 < n){
            for(int j = 0; j < m; j++){
                if(s[i + d + 1][j] == 'S'){
                    l = max(0,j - d);
                    r = min(m-1, j + d);
                    type = 1;
                    dfs(0,0);
                }
            }
        }
    }
    cout << ans;
}

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