제출 #520272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
520272		Cyanmond	이상적인 도시 (IOI12_city)	C++17	100 / 100	93 ms	15500 KiB

city

#line 1 "paper.cpp"
#include <bits/stdc++.h>

#line 3 "library2/utility/len.hpp"

template <class Container> int len(const Container&c){
    return static_cast<int>(std::size(c));
}
#line 5 "library2/algorithm/run_length.hpp"

template <class T> std::vector<std::pair<T, int>> RunLength(const std::vector<T> &x) {
    std::vector<std::pair<T, int>> ret;
    if (x.empty()) {
        return ret;
    }
    const int n = len(x);
    for (int l = 0; l < n;) {
        int r = l + 1;
        while (r < n and x[l] == x[r]) {
            ++r;
        }
        ret.push_back({x[l], r - l});
        l = r;
    }
    return ret;
}
#line 3 "library2/utility/int_alias.hpp"

using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 2 "library2/utility/rec_lambda.hpp"

template <class F> class RecursiveLambda {
    F f;

  public:
    explicit constexpr RecursiveLambda(F &&f_) : f(std::forward<F>(f_)) {}
    template <class... Args> constexpr auto operator()(Args &&...args) const {
        return f(*this, std::forward<Args>(args)...);
    }
};

template <class F> constexpr decltype(auto) rec_lambda(F &&f) {
    return RecursiveLambda<F>(std::forward<F>(f));
}
#line 3 "library2/utility/rep.hpp"

class Range {
    struct Iterator {
        int itr;
        constexpr Iterator(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept {
            ++itr;
        }
        constexpr bool operator!=(const Iterator &other) const noexcept {
            return itr != other.itr;
        }
        constexpr int operator*() const noexcept {
            return itr;
        }
    };
    const Iterator first, last;

  public:
    explicit constexpr Range(const int f, const int l) noexcept
        : first(f), last(std::max(f, l)) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr Range rep(const int l, const int r) noexcept {
    return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
    return Range(0, n);
}
#line 3 "library2/utility/scan.hpp"

template <typename T = int> T scan() {
    T ret;
    std::cin >> ret;
    return ret;
}
#line 9 "paper.cpp"

i64 solve1d(std::vector<i64> X, std::vector<i64> Y) {
    const int N = len(X);
    std::map<i64, std::vector<i64>> points;
    for (const int i : rep(N)) {
        points[X[i]].push_back(Y[i]);
    }

    auto parse = [](std::vector<i64> &vec) {
        const int n = len(vec);
        for (const int i : rep(n)) {
            vec[i] -= i;
        }
        const auto res = RunLength(vec);
        std::vector<std::pair<i64, i64>> ret;
        int count = 0;
        for (const auto &[value, length] : res) {
            ret.push_back({value + count, value + count + length});
            count += length;
        }
        return ret;
    };

    std::vector<i64> count(N);
    std::vector<std::vector<int>> tree(N);

    auto make_tree = [&]() {
        std::vector<std::pair<i64, i64>> last;
        int cum = 0;
        int last_f = 0;
        for (auto &[key, vec] : points) {
            std::sort(vec.begin(), vec.end());
            const auto res = parse(vec);
            for (const auto e : res) {
                const auto l = e.first, r = e.second;
                count[cum] = r - l;
                const int l_l = (int)(std::partition_point(last.begin(), last.end(),
                                                           [&](const std::pair<i64, i64> &v) {
                                                               return v.second <= l;
                                                           }) -
                                      last.begin());
                const int l_r = (int)(std::partition_point(last.begin(), last.end(),
                                                           [&](const std::pair<i64, i64> &v) {
                                                               return v.first < r;
                                                           }) -
                                      last.begin());
                for (const int i : rep(l_l, l_r)) {
                    tree[last_f + i].push_back(cum);
                    tree[cum].push_back(last_f + i);
                }
                ++cum;
            }
            last = res;
            last_f = cum - len(res);
        }
        count.erase(std::find_if(count.begin(), count.end(), [](const int v) { return v == 0; }),
                    count.end());
        tree.erase(tree.begin() + len(count), tree.end());
    };
    make_tree();

    // sum[dist(u, v) * count(u) * count(v)]
    i64 ret = 0;
    auto calc = rec_lambda([&](auto &&f, const int v, const int p) -> std::pair<i64, i64> {
        if (v != 0 and tree[v].size() == 1) {
            return {count[v], count[v]};
        }
        i64 dicsum = 0, udcsum = 0;
        for (const int to : tree[v]) {
            if (to == p) {
                continue;
            }
            const auto res = f(to, v);
            ret += res.first * udcsum + dicsum * res.second;
            ret += res.first * count[v];
            dicsum += res.first;
            udcsum += res.second;
        }
        udcsum += count[v];
        return {dicsum + udcsum, udcsum};
    });
    calc(0, N);

    return ret;
}

int DistanceSum(int N, int *X, int *Y) {
    std::vector<i64> x(N), y(N);
    for (const int i : rep(N)) {
        x[i] = X[i];
        y[i] = Y[i];
    }
    return (int)((solve1d(x, y) + solve1d(y, x)) % 1000000000);
}

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45