Submission #522522

#	Time	Username	Problem	Language	Result	Execution time	Memory
522522		Cyanmond	Painting Walls (APIO20_paint)	C++17	63 / 100	1574 ms	12924 KiB

paint

#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/len.hpp"

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

template <class Container, class T> constexpr int lwb(const Container &c, const T &val) {
    return static_cast<int>(std::distance(c.cbegin(), std::lower_bound(c.cbegin(), c.cend(), val)));
}
#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/revrep.hpp"

class ReversedRange {
    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 ReversedRange(const int f, const int l) noexcept
        : first(l - 1), last(std::min(f, l) - 1) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr ReversedRange revrep(const int l, const int r) noexcept {
    return ReversedRange(l, r);
}
constexpr ReversedRange revrep(const int n) noexcept {
    return ReversedRange(0, n);
}
#line 8 "paper.cpp"
// #include "paint.h"

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

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A,
                        std::vector<std::vector<int>> B) {
    auto make_table = [&]() {
        const int s = N - M + 1;

        std::vector<std::vector<int>> likeds(K);
        for (const int i : rep(M)) {
            for (const int j : B[i]) {
                likeds[j].push_back(i);
            }
        }

        std::vector<bool> ret(s);
        SegmentTree<Monoid> seg(M);
        for (const int i : rep(M)) {
            for (const int c : likeds[C[i]]) {
                seg.set((c - i + M) % M, seg.get((c - i + M) % M) + 1);
            }
        }
        if (seg.fold() == M) {
            ret[0] = true;
        }
        for (const int i : rep(s - 1)) {
            const int x = i % M;
            auto form = [&](int c, int p) { return (c - p) < 0 ? c - p + M : c - p; };
            for (const int c : likeds[C[i + M]]) {
                seg.set(form(c, x), seg.get(form(c, x)) + 1);
            }
            for (const int c : likeds[C[i]]) {
                seg.set(form(c, x), seg.get(form(c, x)) - 1);
            }
            if (seg.fold() == M) {
                ret[i + 1] = true;
            }
        }

        return ret;
    };

    auto calc_answer = [M](std::vector<bool> d) {
        const int s = len(d);
        std::vector<int> r_min(s);
        r_min[s - 1] = d[s - 1] ? s - 1 : s;
        for (const int i : revrep(s - 1)) {
            r_min[i] = d[i] ? i : r_min[i + 1];
        }
        if (r_min[s - 1] == s) {
            return -1;
        }
        int answer = 1, now = s - 1;
        while (now != 0) {
            const int nxt = r_min[std::max(0, now - M)];
            if (nxt == now) {
                return -1;
            }
            ++answer;
            now = nxt;
        }
        return answer;
    };

    const auto table = make_table();
    return calc_answer(table);
}

/*
int main() {
    int N, M, K;
    assert(3 == scanf("%d %d %d", &N, &M, &K));

    std::vector<int> C(N);
    for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &C[i]));
    }

    std::vector<int> A(M);
    std::vector<std::vector<int>> B(M);
    for (int i = 0; i < M; ++i) {
        assert(1 == scanf("%d", &A[i]));
        B[i].resize(A[i]);
        for (int j = 0; j < A[i]; ++j) {
            assert(1 == scanf("%d", &B[i][j]));
        }
    }

    int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
    printf("%d\n", minimum_instructions);
}
*/

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 0 / 37