Submission #137635

#	Time	Username	Problem	Language	Result	Execution time	Memory
137635		hamzqq9	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	88 ms	42888 KiB

mushrooms

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 2000000000
#define N 500005
#define MOD 1000000007
using namespace std;

struct Q {

	int l,r,v;

};

int n,m,d,k,ans;
vector<Q> L[N];
vector<int> M[N];
char s[N];
int S[N<<2],lazy[N<<2];

void shift(int node,int val) {

	S[node]+=val;
	lazy[node]+=val;

}

void push(int node) {

	shift(node<<1,lazy[node]);
	shift(node<<1|1,lazy[node]);

	lazy[node]=0;

}

int get(int node,int bas,int son,int x) {

	if(bas>x || son<x) return -1;

	if(bas>=x && son<=x) return S[node];

	push(node);

	return max(get(node<<1,bas,orta,x),get(node<<1|1,orta+1,son,x));

}

void up(int node,int bas,int son,int x,int y,int val) {

	if(bas>y || son<x) return ;

	if(bas>=x && son<=y) {

		shift(node,val);

		return ;

	}

	push(node);

	up(node<<1,bas,orta,x,y,val);
	up(node<<1|1,orta+1,son,x,y,val);

	S[node]=max(S[node<<1],S[node<<1|1]);

}

int main() {

	scanf("%d %d %d %d",&n,&m,&d,&k);

	for(int i=1;i<=n;i++) {

		scanf("%s",s+1);

		for(int j=1;j<=m;j++) {

			if(s[j]=='M') {

				M[j].pb(i);

			}
			else if(s[j]=='S') {

				int l=max(1,j-d);
				int r=min(m,j+d);
				int u=max(1,i-d);
				int dd=min(n,i+d);

				L[l].pb({u,dd,1});
				L[r+1].pb({u,dd,-1});

			}

		}

	}

	for(int i=1;i<=m;i++) {

		for(auto x:L[i]) up(1,1,n,x.l,x.r,x.v);
		for(auto x:M[i]) ans+=(get(1,1,n,x)>=k);

	}

	printf("%d",ans);

}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&n,&m,&d,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",s+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