Submission #242378

#	Time	Username	Problem	Language	Result	Execution time	Memory
242378		mhy908	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	93 ms	41464 KiB

mushrooms

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
#define ub(x, v) upper_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=2000000000000000000;
const LL mod1=1000000007;
const LL mod2=998244353;
const int inf=2000000000;

struct FENWICK{
    int tree[500010];
    int sum(int i){
        LL ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    int update(int i, int num){
        while(i<=500000){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
    void cl(){memset(tree, 0, sizeof tree);}
}fen;
int n, m, r, k, p;
vector<char> arr[500010];
vector<int> ans[500010];


vector<int> ndel[500010];
int main(){
    scanf("%d %d %d %d", &n, &m, &r, &k);
    for(int i=1; i<=n; i++){
        arr[i].resize(m+1);
        ans[i].resize(m+1);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf(" %c", &arr[i][j]);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(arr[i][j]=='S'){
                fen.update(max(1, j-r), 1);
                fen.update(min(m, j+r)+1, -1);
                if(i+r<n)ndel[i+r+1].eb(j);
            }
        }
        for(auto j:ndel[i]){
            fen.update(max(1, j-r), -1);
            fen.update(min(m, j+r)+1, 1);
        }
        ndel[i].clear();
        for(int j=1; j<=m; j++){
            if(arr[i][j]=='M'){
                ans[i][j]+=fen.sum(j);
            }
        }
    }
    fen.cl();
    for(int i=n; i>=1; i--){
        for(auto j:ndel[i]){
            fen.update(max(1, j-r), -1);
            fen.update(min(m, j+r)+1, 1);
        }
        ndel[i].clear();
        for(int j=1; j<=m; j++){
            if(arr[i][j]=='M'){
                ans[i][j]+=fen.sum(j);
                if(ans[i][j]>=k)p++;
            }
        }
        for(int j=1; j<=m; j++){
            if(arr[i][j]=='S'){
                fen.update(max(1, j-r), 1);
                fen.update(min(m, j+r)+1, -1);
                if(i-r>1)ndel[i-r-1].eb(j);
            }
        }
    }
    printf("%d", p);
}

Compilation message (stderr)

mushrooms.cpp: In member function 'int FENWICK::update(int, int)':
mushrooms.cpp:37:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
mushrooms.cpp: In function 'int main()':
mushrooms.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &m, &r, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &arr[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