oj.uz

Submission #521241

# Submission time Handle Problem Language Result Execution time Memory
521241 2022-02-01T09:34:22 Z KoD Strah (COCI18_strah) C++17
110 / 110
 423 ms 24132 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 844 KB Output is correct
2 Correct 10 ms 892 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 844 KB Output is correct
2 Correct 11 ms 844 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 900 KB Output is correct
2 Correct 11 ms 884 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 6564 KB Output is correct
2 Correct 247 ms 14532 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 14908 KB Output is correct
2 Correct 364 ms 21956 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 9596 KB Output is correct
2 Correct 259 ms 15816 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1996 KB Output is correct
2 Correct 308 ms 17816 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 24064 KB Output is correct
2 Correct 423 ms 24132 KB Output is correct