Submission #1314006

#TimeUsernameProblemLanguageResultExecution timeMemory
1314006levCollecting Mushrooms (NOI18_collectmushrooms)C++20
100 / 100
29 ms16972 KiB
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int r, c, d, k;
vector<vector<char>> a;
vector<vector<int>> bit;

void add(int x, int y, int val){
	for(int i = x; i <= r; i += i & -i){
		for(int j = y; j <= c; j += j & -j){
			bit[i][j] += val;
		}
	}
}

int get(int x, int y){
	int r = 0;
	for(int i = x; i; i -= i & -i){
		for(int j = y; j; j -= j & -j){
			r += bit[i][j];
		}
	}
	return r;
}

void solve() {
    cin >> r >> c >> d >> k;
    a.resize(r + 5, vector <char> (c + 5));
    bit.resize(r + 5, vector <int> (c + 5));
    for(int i = 1; i <= r; i++){
    	for(int j = 1; j <= c; j++){
    		cin >> a[i][j];
    		if(a[i][j] == 'S'){
    			int x1 = max(i - d, 1);
    			int y1 = max(j - d, 1);
    			int x2 = min(i + d, r);
    			int y2 = min(j + d, c);
    			debug(x1, y1, x2, y2);
    			add(x1, y1, 1);
    			add(x1, y2 + 1, -1);
    			add(x2 + 1, y1, -1);
    			add(x2 + 1, y2 + 1, 1);
    		}
    	}
    }
    int res = 0;
    for(int i = 1; i <= r; i++){
    	for(int j = 1; j <= c; j++){
    		if(a[i][j] == 'M'){
    			int val = get(i, j);
    			res += (val >= k);
    		}
    	}
    }
    cout << res << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    #define task "Kawabata"
    if (fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro

Compilation message (stderr)

mushrooms.cpp: In function 'int main()':
mushrooms.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...