#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifdef ONPC
freopen ("input.txt", "r", stdin);
#endif // ONPC
#ifndef ONPC
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC
int n, m, r, need;
cin >> n >> m >> r >> need;
vector<pair<int, int>> mus, spr;
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
assert((int) s.size() == m);
for (int j = 0; j < m; j++)
{
char ch = s[j];
if (ch == '.')
{
continue;
}
if (ch == 'S')
{
spr.push_back({i, j + 1});
continue;
}
if (ch == 'M')
{
mus.push_back({i, j + 1});
continue;
}
assert(0);
}
}
vector<int> t(m + 1, 0);
auto add = [&] (int i, int x)
{
while (i <= m)
{
t[i] += x;
i += i & (-i);
}
};
auto get = [&] (int i)
{
int sol = 0;
while (i)
{
sol += t[i];
i -= i & (-i);
}
return sol;
};
int sol = 0;
sort(mus.begin(), mus.end());
sort(spr.begin(), spr.end());
int p1 = 0, p2 = 0;
for (auto &it : mus)
{
while (p1 < (int) spr.size() && spr[p1].first <= it.first + r)
{
add(spr[p1].second, +1);
p1++;
}
while (p2 < (int) spr.size() && spr[p2].first < it.first - r)
{
add(spr[p2].second, -1);
p2++;
}
int low = max(1, it.second - r), high = min(m, it.second + r);
sol += (get(high) - get(low - 1) >= need);
}
cout << sol << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
5232 KB |
Output is correct |
2 |
Correct |
36 ms |
6440 KB |
Output is correct |
3 |
Correct |
24 ms |
5840 KB |
Output is correct |
4 |
Correct |
31 ms |
6320 KB |
Output is correct |
5 |
Correct |
36 ms |
7660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
20 ms |
5232 KB |
Output is correct |
22 |
Correct |
36 ms |
6440 KB |
Output is correct |
23 |
Correct |
24 ms |
5840 KB |
Output is correct |
24 |
Correct |
31 ms |
6320 KB |
Output is correct |
25 |
Correct |
36 ms |
7660 KB |
Output is correct |
26 |
Correct |
12 ms |
3092 KB |
Output is correct |
27 |
Correct |
15 ms |
3220 KB |
Output is correct |
28 |
Correct |
17 ms |
3828 KB |
Output is correct |
29 |
Correct |
11 ms |
2508 KB |
Output is correct |
30 |
Correct |
13 ms |
3684 KB |
Output is correct |