Submission #854562

#	Time	Username	Problem	Language	Result	Execution time	Memory
854562		MilosMilutinovic	Collecting Mushrooms (NOI18_collectmushrooms)	C++14	100 / 100	37 ms	50684 KiB

mushrooms

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int r,c,d,k,fenw[500005],cnt[500005];
char s[500005];
vector<pii> a,b;
vector<int> qs[500005][3];

void update(int p,int v){
	for(;p<500005;p+=p&-p) fenw[p]+=v;
}
int query(int p){
	int res=0;
	for(;p>0;p-=p&-p) res+=fenw[p];
	return res;
}
int query(int l,int r){
	return query(r)-query(l-1);
}

int main(){
	r=readint(); c=readint(); d=readint(); k=readint();
	for(int i=1;i<=r;i++){
		scanf("%s",s+1);
		for(int j=1;j<=c;j++){
			if(s[j]=='M') a.pb(mp(i,j));
			if(s[j]=='S') b.pb(mp(i,j));
		}
	}
	for(int i=0;i<(int)a.size();i++){
		qs[max(1,a[i].fi-d)][0].pb(i);
		qs[min(r,a[i].fi+d)][1].pb(i);
	}
	for(int i=0;i<(int)b.size();i++){
		qs[b[i].fi][2].pb(i);
	}
	for(int i=1;i<=r;i++){
		for(int j:qs[i][0]) cnt[j]-=query(max(1,a[j].se-d),min(c,a[j].se+d));
		for(int j:qs[i][2]) update(b[j].se,+1);
		for(int j:qs[i][1]) cnt[j]+=query(max(1,a[j].se-d),min(c,a[j].se+d));
	}
	int ans=0;
	for(int i=0;i<(int)a.size();i++) if(cnt[i]>=k) ans++;
	printf("%d\n",ans);
	return 0;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   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