oj.uz

Submission #137636

# Submission time Handle Problem Language Result Execution time Memory
137636 2019-07-28T07:54:26 Z ekrem Collecting Mushrooms (NOI18_collectmushrooms) C++
100 / 100
 263 ms 121404 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 102344 KB Output is correct
2 Correct 95 ms 102264 KB Output is correct
3 Correct 94 ms 102208 KB Output is correct
4 Correct 94 ms 102136 KB Output is correct
5 Correct 93 ms 102136 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 102344 KB Output is correct
2 Correct 95 ms 102264 KB Output is correct
3 Correct 94 ms 102208 KB Output is correct
4 Correct 94 ms 102136 KB Output is correct
5 Correct 93 ms 102136 KB Output is correct
6 Correct 94 ms 102160 KB Output is correct
7 Correct 108 ms 102136 KB Output is correct
8 Correct 96 ms 102264 KB Output is correct
9 Correct 94 ms 102136 KB Output is correct
10 Correct 93 ms 102136 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 102136 KB Output is correct
2 Correct 94 ms 102264 KB Output is correct
3 Correct 94 ms 102264 KB Output is correct
4 Correct 94 ms 102264 KB Output is correct
5 Correct 93 ms 102264 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 102304 KB Output is correct
2 Correct 113 ms 102504 KB Output is correct
3 Correct 109 ms 102480 KB Output is correct
4 Correct 106 ms 102392 KB Output is correct
5 Correct 107 ms 102392 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 111700 KB Output is correct
2 Correct 167 ms 117620 KB Output is correct
3 Correct 167 ms 114308 KB Output is correct
4 Correct 263 ms 121404 KB Output is correct
5 Correct 199 ms 118976 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 102344 KB Output is correct
2 Correct 95 ms 102264 KB Output is correct
3 Correct 94 ms 102208 KB Output is correct
4 Correct 94 ms 102136 KB Output is correct
5 Correct 93 ms 102136 KB Output is correct
6 Correct 94 ms 102160 KB Output is correct
7 Correct 108 ms 102136 KB Output is correct
8 Correct 96 ms 102264 KB Output is correct
9 Correct 94 ms 102136 KB Output is correct
10 Correct 93 ms 102136 KB Output is correct
11 Correct 94 ms 102136 KB Output is correct
12 Correct 94 ms 102264 KB Output is correct
13 Correct 94 ms 102264 KB Output is correct
14 Correct 94 ms 102264 KB Output is correct
15 Correct 93 ms 102264 KB Output is correct
16 Correct 107 ms 102304 KB Output is correct
17 Correct 113 ms 102504 KB Output is correct
18 Correct 109 ms 102480 KB Output is correct
19 Correct 106 ms 102392 KB Output is correct
20 Correct 107 ms 102392 KB Output is correct
21 Correct 189 ms 111700 KB Output is correct
22 Correct 167 ms 117620 KB Output is correct
23 Correct 167 ms 114308 KB Output is correct
24 Correct 263 ms 121404 KB Output is correct
25 Correct 199 ms 118976 KB Output is correct
26 Correct 159 ms 105624 KB Output is correct
27 Correct 145 ms 104704 KB Output is correct
28 Correct 205 ms 107712 KB Output is correct
29 Correct 163 ms 105224 KB Output is correct
30 Correct 147 ms 105440 KB Output is correct