Submission #70989473

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;

struct Node {
    valueType x, y;
    valueType height, weight;

    Node() = default;
    Node(valueType const x, valueType const y, valueType const height, valueType const weight)
        : x(x), y(y), height(height), weight(weight) {}

    valueType size() const {
        return height * weight;
    }
};

bool Adjacent(Node const &A, Node const &B) {
    bool result = false;

    result = result || (((A.x + A.height == B.x) || (B.x + B.height == A.x)) && !((A.y + A.weight <= B.y) || (B.y + B.weight <= A.y)));
    result = result || (((A.y + A.weight == B.y) || (B.y + B.weight == A.y)) && !((A.x + A.height <= B.x) || (B.x + B.height <= A.x)));

    return result;
}

typedef std::vector<Node> NodeVector;

template<typename T, bool SizeBalanced>
class DSU {};

template<typename T>
class DSU<T, false> {
private:
    T N;
    std::vector<T> father;

public:
    DSU() = default;

    explicit DSU(T n) : N(n), father(N) {
        std::iota(father.begin(), father.end(), 0);
    }

    void resize(T n) {
        N = n;
        father.resize(N);
        std::iota(father.begin(), father.end(), 0);
    }

public:
    T find(T x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    bool merge(T x, T y) { // merge y to x
        if (find(x) == find(y))
            return false;

        father[find(y)] = find(x);

        return true;
    }
};

template<typename T>
class DSU<T, true> {
private:
    T N;
    std::vector<T> father;
    std::vector<T> size;

public:
    DSU() = default;

    explicit DSU(T n) : N(n), father(N), size(N, 1) {
        std::iota(father.begin(), father.end(), 0);
    }

    void resize(T n) {
        N = n;
        father.resize(N);
        size.resize(N);
        std::iota(father.begin(), father.end(), 0);
        std::fill(size.begin(), size.end(), 1);
    }

public:
    T find(T x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    bool merge(T x, T y) { // merge y to x
        if (find(x) == find(y))
            return false;

        if (size[find(x)] < size[find(y)])
            std::swap(x, y);

        father[find(y)] = find(x);
        size[find(x)] += size[find(y)];

        return true;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, X, Y;

    std::cin >> N >> X >> Y;

    NodeVector Nodes(1, Node(0, 0, X, Y));

    for (valueType n = 0; n < N; ++n) {
        NodeVector New;

        char direction;
        valueType A, B;

        std::cin >> direction >> A >> B;

        if (direction == 'X') {
            for (auto const &node : Nodes) {
                if (node.x < A && A <= node.x + node.height - 1) {
                    New.emplace_back(node.x, node.y - B, A - node.x, node.weight);
                    New.emplace_back(A, node.y + B, node.x + node.height - A, node.weight);
                } else if (node.x + node.height - 1 < A) {
                    New.emplace_back(node.x, node.y - B, node.height, node.weight);
                } else { // A <= node.x
                    New.emplace_back(node.x, node.y + B, node.x + node.height, node.weight);
                }
            }
        } else {
            for (auto const &node : Nodes) {
                if (node.y < A && A <= node.y + node.weight - 1) {
                    New.emplace_back(node.x - B, node.y, node.height, A - node.y);
                    New.emplace_back(node.x + B, A, node.height, node.y + node.weight - A);
                } else if (node.y + node.weight - 1 < A) {
                    New.emplace_back(node.x - B, node.y, node.height, node.weight);
                } else { // A <= node.y
                    New.emplace_back(node.x + B, node.y, node.height, node.weight);
                }
            }
        }

        Nodes.swap(New);
    }

    valueType const size = Nodes.size();

    DSU<int, false> dsu(size);

    for (valueType i = 0; i < size; ++i) {
        for (valueType j = 0; j < i; ++j) {
            if (Adjacent(Nodes[i], Nodes[j]))
                dsu.merge(i, j);
        }
    }

    ValueVector Ans(size, 0);

    for (valueType i = 0; i < size; ++i)
        Ans[dsu.find(i)] += Nodes[i].size();

    std::sort(Ans.begin(), Ans.end(), std::greater<valueType>());

    while (Ans.back() == 0)
        Ans.pop_back();

    std::sort(Ans.begin(), Ans.end());

    std::cout << Ans.size() << std::endl;

    for (auto const &ans : Ans)
        std::cout << ans << " ";

    std::cout << std::endl;
}

Submission Info

Judge Result