oj.uz

Submission #520272

# Submission time Handle Problem Language Result Execution time Memory
520272 2022-01-29T04:46:20 Z Cyanmond Ideal city (IOI12_city) C++17
100 / 100
 93 ms 15500 KB 
#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.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
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 3 ms 556 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 432 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2472 KB Output is correct
2 Correct 11 ms 2612 KB Output is correct
3 Correct 24 ms 5696 KB Output is correct
4 Correct 21 ms 5752 KB Output is correct
5 Correct 51 ms 11236 KB Output is correct
6 Correct 46 ms 11272 KB Output is correct
7 Correct 56 ms 11288 KB Output is correct
8 Correct 57 ms 11212 KB Output is correct
9 Correct 46 ms 11276 KB Output is correct
10 Correct 93 ms 15500 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2724 KB Output is correct
2 Correct 13 ms 2704 KB Output is correct
3 Correct 36 ms 6268 KB Output is correct
4 Correct 38 ms 6184 KB Output is correct
5 Correct 87 ms 12304 KB Output is correct
6 Correct 70 ms 11604 KB Output is correct
7 Correct 88 ms 12396 KB Output is correct
8 Correct 59 ms 11616 KB Output is correct
9 Correct 63 ms 11380 KB Output is correct
10 Correct 48 ms 11236 KB Output is correct