Submission #521887

#	Time	Username	Problem	Language	Result	Execution time	Memory
521887		Cyanmond	Pairs (IOI07_pairs)	C++17	100 / 100	344 ms	45520 KiB

pairs

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

#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 7 "library2/data-structure/segmenttree.hpp"

template <class M> class SegmentTree {
  public:
    using size_type = int;
    using value_type = typename M::value_type;

  private:
    size_type m_n, m_size;
    std::vector<value_type> m_nodes;

  public:
    explicit SegmentTree(const size_type n) : m_n(n), m_size(ceil_pow2(n)) {
        m_nodes.assign(m_size << 1, M::identity());
    }

    SegmentTree(const size_type n, const value_type v) {
        *this = SegmentTree(std::vector(n, v));
    }

    SegmentTree(const std::vector<value_type> &s) : m_n(s.size()), m_size(ceil_pow2(s.size())) {
        m_nodes.assign(m_size << 1, M::identity());
        std::copy(s.begin(), s.end(), m_nodes.begin() + m_size);
        for (size_type i = m_size - 1; i != 0; --i)
            internal_update(i);
    }

    void set(size_type i, const value_type &v) {
        assert(i < m_n);
        i += m_size;
        m_nodes[i] = v;
        for (i >>= 1; i != 0; i >>= 1)
            internal_update(i);
    }

    value_type fold() const {
        return m_nodes[1];
    }

    value_type fold(size_type l, size_type r) const {
        assert(l <= r);
        assert(r <= m_n);
        value_type v_l = M::identity(), v_r = M::identity();
        for (l += m_size, r += m_size; l < r; l >>= 1, r >>= 1) {
            if (l & 1) v_l = M::operation(v_l, m_nodes[l++]);
            if (r & 1) v_r = M::operation(m_nodes[--r], v_r);
        }
        return M::operation(v_l, v_r);
    }

    value_type get(const size_type i) const {
        assert(i < m_n);
        return m_nodes[m_size + i];
    }

    template <class F> size_type max_right(size_type l, const F &f) const {
        assert(l <= m_n);
        assert(f(M::identity()));
        if (l == m_n) return m_n;

        l += m_size;
        value_type sum = M::identity();
        do {
            while (not(l & 1))
                l >>= 1;
            if (not f(M::operation(sum, m_nodes[l]))) {
                while (l < m_size) {
                    l = l << 1;
                    if (f(M::operation(sum, m_nodes[l]))) sum = M::operation(sum, m_nodes[l++]);
                }
                return l - m_size;
            }
            sum = M::operation(sum, m_nodes[l++]);
        } while ((l & (l - 1)) != 0);
        return m_n;
    }

    template <class F> size_type min_left(size_type r, const F &f) const {
        assert(r <= m_n);
        assert(f(M::identity()));
        if (r == 0) return 0;

        r += m_size;
        value_type sum = M::identity();
        do {
            --r;
            while (r > 1 and (r & 1))
                r >>= 1;
            if (not f(M::operation(m_nodes[r], sum))) {
                while (r < m_size) {
                    r = (r << 1) | 1;
                    if (f(M::operation(m_nodes[r], sum))) sum = M::operation(m_nodes[r--], sum);
                }
                return r + 1 - m_size;
            }
            sum = M::operation(m_nodes[r], sum);
        } while ((r & (r - 1)) != 0);
        return 0;
    }

  private:
    static constexpr size_type ceil_pow2(const size_type n_) noexcept {
        size_type res = 1;
        while (res < n_)
            res <<= 1;
        return res;
    }

    void internal_update(const size_type i) {
        m_nodes[i] = M::operation(m_nodes[i << 1], m_nodes[i << 1 | 1]);
    }
};
#line 3 "library2/utility/int_literal.hpp"

constexpr i8 operator""_i8(unsigned long long n) noexcept {
    return static_cast<i8>(n);
}
constexpr i16 operator""_i16(unsigned long long n) noexcept {
    return static_cast<i16>(n);
}
constexpr i32 operator""_i32(unsigned long long n) noexcept {
    return static_cast<i32>(n);
}
constexpr i64 operator""_i64(unsigned long long n) noexcept {
    return static_cast<i64>(n);
}
constexpr u8 operator""_u8(unsigned long long n) noexcept {
    return static_cast<u8>(n);
}
constexpr u16 operator""_u16(unsigned long long n) noexcept {
    return static_cast<u16>(n);
}
constexpr u32 operator""_u32(unsigned long long n) noexcept {
    return static_cast<u32>(n);
}
constexpr u64 operator""_u64(unsigned long long n) noexcept {
    return static_cast<u64>(n);
}
#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 2 "library2/utility/setmin.hpp"

template <typename T> bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
#line 5 "library2/utility/upb.hpp"

template <class Container, class T> constexpr int upb(const Container &c, const T &val) {
    return static_cast<int>(std::distance(c.cbegin(), std::upper_bound(c.cbegin(), c.cend(), val)));
}
#line 10 "paper.cpp"

i64 solve_1() {
    const int N = scan();
    const i64 D = scan();
    [[maybe_unused]] const i64 M = scan();
    std::vector<i64> C(N);
    for (auto &e : C) {
        e = scan() - 1;
    }
    std::sort(C.begin(), C.end());
    i64 answer = 0;
    for (const int i : rep(N)) {
        answer += upb(C, C[i] + D) - i - 1;
    }
    return answer;
}

void rotate45(int &a, int &b) {
    int c = a - b, d = a + b;
    a = c, b = d;
}

struct Monoid {
    using value_type = int;
    static int operation(int a, int b) {
        return a + b;
    }
    static int identity() {
        return 0;
    }
};

i64 solve_2() {
    const int N = scan();
    const int D = scan();
    const int M = scan();
    std::vector<int> A(N), B(N);
    for (const int i : rep(N)) {
        A[i] = scan() - 1;
        B[i] = scan() - 1;
        rotate45(A[i], B[i]);
    }

    {
        const int min =
            std::min(*std::min_element(B.begin(), B.end()), *std::min_element(A.begin(), A.end()));
        for (auto &e : A) {
            e -= min;
        }
        for (auto &e : B) {
            e -= min;
        }
    }

    std::map<int, std::vector<int>> add_events;
    std::map<int, std::vector<std::tuple<bool, int, int, int>>> sum_events;
    std::vector<int> p;
    p.reserve(3 * N);
    for (const int i : rep(N)) {
        p.push_back(A[i]);
        p.push_back(A[i] - D);
        p.push_back(A[i] + D + 1);
        add_events[A[i]].push_back(B[i]);
        sum_events[A[i] - D].push_back({false, i, B[i] - D, B[i] + D + 1});
        sum_events[A[i] + D + 1].push_back({true, i, B[i] - D, B[i] + D + 1});
    }
    std::sort(p.begin(), p.end());
    p.erase(std::unique(p.begin(), p.end()), p.end());

    SegmentTree<Monoid> seg(5 * M);
    std::vector<int> res(N);
    for (const auto a : p) {
        if (sum_events.find(a) != sum_events.end()) {
            for (const auto &[type, idx, l, r] : sum_events[a]) {
                const int sum = seg.fold(std::max(0, l), std::min(5 * M, r));
                if (type) {
                    res[idx] += sum;
                } else {
                    res[idx] -= sum;
                }
            }
        }
        if (add_events.find(a) != add_events.end()) {
            for (const auto e : add_events[a]) {
                seg.set(e, seg.get(e) + 1);
            }
        }
    }

    return (std::accumulate(res.begin(), res.end(), 0_i64) - N) / 2;
}

i64 solve_3() {
    const int N = scan();
    const int D = scan();
    const int M = scan();
    std::vector<int> A(N), B(N), C(N);
    std::vector data(M, std::vector(5 * M + 1, std::vector(5 * M + 1, 0)));
    for (const int i : rep(N)) {
        A[i] = scan() - 1;
        B[i] = scan() - 1;
        C[i] = scan() - 1;
        rotate45(B[i], C[i]);
    }
    {
        const int min =
            std::min(*std::min_element(B.begin(), B.end()), *std::min_element(C.begin(), C.end()));
        for (auto &e : B) {
            e -= min;
        }
        for (auto &e : C) {
            e -= min;
        }
    }

    for (const int i : rep(N)) {
        ++data[A[i]][B[i] + 1][C[i] + 1];
    }

    for (const int i : rep(M)) {
        for (const int j : rep(5 * M + 1)) {
            for (const int k : rep(5 * M)) {
                data[i][j][k + 1] += data[i][j][k];
            }
        }
        for (const int j : rep(5 * M)) {
            for (const int k : rep(5 * M + 1)) {
                data[i][j + 1][k] += data[i][j][k];
            }
        }
    }

    auto calc_sum = [&](const int h, const int r1, const int c1, const int r2, const int c2) {
        return data[h][r2][c2] - data[h][r1][c2] - data[h][r2][c1] + data[h][r1][c1];
    };

    i64 answer = 0;
    for (const int i : rep(N)) {
        for (const int j : rep(M)) {
            const int diff = std::abs(A[i] - j);
            if (diff > D) {
                continue;
            } else {
                int s = D - diff;
                answer += calc_sum(j, std::max(0, B[i] - s), std::max(0, C[i] - s),
                                   std::min(5 * M, B[i] + s + 1), std::min(5 * M, C[i] + s + 1));
            }
        }
    }

    return (answer - N) / 2;
}

int main() {
    const int B = scan();
    const i64 answer = (B == 1 ? solve_1() : (B == 2 ? solve_2() : solve_3()));
    std::cout << answer << std::endl;
}

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