Submission #1314321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1314321		layk	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	100 / 100	16 ms	12748 KiB

mushrooms

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <immintrin.h>

#ifndef DEBUG
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#endif

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
//
using ld = long double;
using ll = long long;
using i128 = __int128;
using ull = unsigned long long;
using pll = std::pair<ll, ll>;
using cmpl = std::complex<ld>;
template<typename T>
using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr ll MOD1 = 998244353;
constexpr ll MOD = 1000000007;
constexpr ll INV2 = 499122177;
constexpr ld PI = 3.141592653589793;
const ld eps = 1e-7;
const ll K = 500;
//const ll C = 200;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

ld START_TIME = clock();

struct Fenwick{
    std::vector<std::vector<ll>> f;

    Fenwick(ll n, ll m){
        f.resize(n + 1, std::vector<ll>(m + 1));
    }

    void add(ll i, ll j){
        ++i, ++j;
        while (i < f.size()){
            ll j1 = j;
            while (j1 < f[i].size()){
                ++f[i][j1];
                j1 += j1 & -j1;
            }
            i += i & -i;
        }
    }

    ll get(ll x, ll y){
        ll ans = 0;
        while (x > 0){
            ll j = y;
            while (j > 0){
                ans += f[x][j];
                j -= j & -j;
            }
            x -= x & -x;
        }
        return ans;
    }

    ll get(ll x, ll y, ll x1, ll y1){
        ll ddv = get(x1, y1) + get(x, y);
        return ddv - get(x1, y) - get(x, y1);
    }
};

void solve() {
    ll n, m, d, k;
    std::cin >> n >> m >> d >> k;
    std::vector<std::string> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    Fenwick f(n, m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] == 'S'){
                f.add(i, j);
            }
        }
    }
    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < m; ++j) {
            if (a[i][j] == 'M'){
                ll cnt = f.get(std::max(0ll, i - d), std::max(0ll, j - d), std::min(i + d + 1, n), std::min(j + d + 1, m));
                ans += cnt >= k;
            }
        }
    }
    std::cout << ans;
}

signed main() {
#ifdef DEBUG
    std::freopen("/home/anton/CLionProjects/untitled/input.txt", "r", stdin);
#else
    //    std::freopen("tri.in", "r", stdin); std::freopen("tri.out", "w", stdout);
#endif
    std::cin.tie(nullptr)->std::ios_base::sync_with_stdio(false);
    int tt = 1;
    //    ll g; std::cin >> g;
//    std::cin >> tt;
    while (tt--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << '\n';
    ld TIME = (clock() - START_TIME) / CLOCKS_PER_SEC;
    std::cerr << "Time: " << TIME << '\n';
#endif
}

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