Submission #586333

#	Time	Username	Problem	Language	Result	Execution time	Memory
586333		krit3379	Collecting Mushrooms (NOI18_collectmushrooms)	C++17	100 / 100	29 ms	15444 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005

int n,m,d,k,ans;
vector<vector<int>> fen;

void upd(int x,int y,int k){
    x=max(x,1),y=max(y,1);
    for(int i=x;i<=n;i+=i&-i)for(int j=y;j<=m;j+=j&-j)fen[i][j]+=k;
}

void upd_rec(int x,int y){
    upd(x-d,y-d,1);
    upd(x-d,y+d+1,-1);
    upd(x+d+1,y-d,-1);
    upd(x+d+1,y+d+1,1);
}

int query(int x,int y){
    x=min(x,n),y=min(y,m);
    int ans=0;
    for(int i=x;i>0;i-=i&-i)for(int j=y;j>0;j-=j&-j)ans+=fen[i][j];
    return ans;
}

int main(){
    int i,j;
    scanf("%d %d %d %d",&n,&m,&d,&k);
    char s[n+5][m+5];
    for(i=1;i<=n;i++)scanf(" %s",s[i]+1);
    fen.resize(n+5);
    for(i=0;i<n+5;i++)fen[i].resize(m+5);
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(s[i][j]=='S')upd_rec(i,j);
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(s[i][j]=='M'&&query(i,j)>=k)ans++;
    printf("%d",ans);
    return 0;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d %d %d",&n,&m,&d,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:33:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     for(i=1;i<=n;i++)scanf(" %s",s[i]+1);
      |                      ~~~~~^~~~~~~~~~~~~~

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