Submission #137636

#	Time	Username	Problem	Language	Result	Execution time	Memory
137636		ekrem	Collecting Mushrooms (NOI18_collectmushrooms)	C++98	100 / 100	263 ms	121404 KiB

mushrooms

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i]
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)>>1)
#define mod 1000000007
#define inf 1000000009
#define N 1000005

using namespace std;

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

int n, m, d, k, ans, fen[N];
string s[N];
vector < ii > ek[N], cik[N];
vector < int > g[N];

void up(int x, int y){
	for(;x < N; x += -x&x)
		fen[x] += y;
}

int qu(int x){
	int ans = 0;
	for(;x > 0; x-= -x&x)
		ans += fen[x];
	return ans;
}

int main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m >> d >> k;
	for(int i = 1; i <= n; i++){
		cin >> s[i];
		s[i] = "0" + s[i];
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			if(s[i][j] == 'S'){
				// cout << i << " " << j << endl;
				ek[max(j - d, 1)].pb(mp(max(1, i - d), min(n, i + d) ));
				cik[min(j + d, m)].pb(mp(max(1, i - d), min(n, i + d) ));
			} else if(s[i][j] == 'M'){
				g[j].pb(i);
			}
	for(int i = 1; i <= m; i++){
		// cout << i << " " << ek[i].size() << " " << cik[i].size() << endl;
		for(int j = 0; j < ek[i].size(); j++){
			up(ek[i][j].st, 1);
			up(ek[i][j].nd + 1, -1);
		}

		// for(int i = 1; i <= n; i++)cout << qu(i) - qu(i - 1) << " ";cout << endl;

		for(int j = 0; j < g[i].size(); j++){
			int x = qu(g[i][j]);
			if(x >= k)
				ans++;
		}

		for(int j = 0; j < cik[i].size(); j++){
			up(cik[i][j].st, -1);
			up(cik[i][j].nd + 1, +1);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < ek[i].size(); j++){
                  ~~^~~~~~~~~~~~~~
mushrooms.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[i].size(); j++){
                  ~~^~~~~~~~~~~~~
mushrooms.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < cik[i].size(); j++){
                  ~~^~~~~~~~~~~~~~~

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