제출 #137635

#제출 시각아이디문제언어결과실행 시간메모리
137635hamzqq9Collecting Mushrooms (NOI18_collectmushrooms)C++14
100 / 100
88 ms42888 KiB
#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);

}

컴파일 시 표준 에러 (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);
   ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...