Submission #521241

#	Time	Username	Problem	Language	Result	Execution time	Memory
521241		KoD	Strah (COCI18_strah)	C++17	110 / 110	423 ms	24132 KiB

strah

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

template <class F> struct rec_lambda : private F {
    explicit rec_lambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

ll sum_linear(const ll a, const ll b) {
    return (a + b) * (b - a + 1) / 2;  
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector grid(N, vector<char>(M));
    for (auto& v : grid) {
        for (auto& x : v) {
            std::cin >> x;
        }
    }
    vector down(N + 1, vector<int>(M));
    for (int i = N - 1; i >= 0; --i) {
        for (int j = 0; j < M; ++j) {
            if (grid[i][j] == '.') {
                down[i][j] = down[i + 1][j] + 1;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        vector<int> parent(M, -1), stack;
        for (int j = 0; j < M; ++j) {
            int prev = -1;
            while (!stack.empty() and down[i][stack.back()] > down[i][j]) {
                prev = stack.back();
                stack.pop_back();
            }
            if (prev != -1) {
                parent[prev] = j;
            }
            if (!stack.empty()) {
                parent[j] = stack.back();
            }
            stack.push_back(j);
        }
        int root = -1;
        vector<vector<int>> child(M);
        for (int j = 0; j < M; ++j) {
            if (parent[j] == -1) {
                root = j;
            } else {
                child[parent[j]].push_back(j);
            }
        }
        rec_lambda([&](auto&& dfs, const int l, const int r, const int m) -> void {
            ans += (sum_linear(m + 1, r) * (m - l + 1) - sum_linear(l, m) * (r - m)) * sum_linear(0, down[i][m]);
            for (const int c : child[m]) {
                if (c < m) {
                    dfs(l, m, c);
                } else {
                    dfs(m + 1, r, c);
                }
            }
        })(0, M, root);
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11