This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[100010];
int sum(int i){
LL ans=0;
while(i){
ans+=tree[i];
i-=(i&-i);
}
return ans;
}
int update(int i, LL num){
while(i<=100000){
tree[i]+=num;
i+=(i&-i);
}
}
void cl(){memset(tree, 0, sizeof tree);}
}fen;
int n, m, r, k, p;
vector<char> arr[100010];
vector<int> ans[100010];
vector<int> ndel[100010];
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, LL)':
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]);
~~~~~^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |