Submission #300289

#	Time	Username	Problem	Language	Result	Execution time	Memory
300289		marX	Comparing Plants (IOI20_plants)	C++17	44 / 100	673 ms	14584 KiB

plants

#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <array>
#include <assert.h>
#include <bitset>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <fstream>
#include <iomanip>

#include <istream>

#include <map>
#include <math.h>
#include <numeric>
#include <ostream>
#include <queue>

#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>

namespace asl
{

    void fin(std::string word)
    {
        std::cout << word << std::endl;
        std::exit(0);
    }

} // namespace asl

#include <stdint.h>

#include <experimental/optional>
#define optional std::experimental::optional

namespace asl
{

    template <typename T, typename U = T>
    class SegmentTree
    {
        int size;
        std::function<void(T &, U &)> _update;
        std::function<T(T &, T &)> _merge;
        std::function<optional<U>(T &)> _get_lazy;

        void push(int p, int l, int r)
        {
            auto lazy = _get_lazy(ds[p]);

            if (lazy)
            {
                _update(ds[l], *lazy);
                _update(ds[r], *lazy);
            }
        }

        void update(int p, int b, int e, int x, int y, U &upd)
        {
            if (x <= b && e <= y)
            {
                _update(ds[p], upd);
            }
            else
            {
                int m = (b + e) >> 1, l = p + 1, r = p + ((m - b) << 1);

                push(p, l, r);

                if (x < m)
                    update(l, b, m, x, y, upd);

                if (m < y)
                    update(r, m, e, x, y, upd);

                ds[p] = _merge(ds[l], ds[r]);
            }
        }

        T query(int p, int b, int e, int x, int y)
        {
            if (x <= b && e <= y)
            {
                return ds[p];
            }
            else
            {
                int m = (b + e) >> 1, l = p + 1, r = p + ((m - b) << 1);

                push(p, l, r);

                if (x < m)
                {
                    auto le = query(l, b, m, x, y);

                    if (m < y)
                    {
                        auto ri = query(r, m, e, x, y);
                        return _merge(le, ri);
                    }
                    else
                    {
                        return le;
                    }
                }
                else
                {
                    return query(r, m, e, x, y);
                }
            }
        }

        void build(int p, int b, int e, std::function<T(int)> &builder)
        {
            if (b + 1 == e)
            {
                ds[p] = builder(b);
            }
            else
            {
                int m = (b + e) >> 1, l = p + 1, r = p + ((m - b) << 1);

                build(l, b, m, builder);
                build(r, m, e, builder);

                ds[p] = _merge(ds[l], ds[r]);
            }
        }

        void init(int size,
                  std::function<void(T &, U &)> update,
                  std::function<T(T &, T &)> merge,
                  std::function<optional<U>(T &)> get_lazy)
        {
            this->size = size;
            this->_update = update;
            this->_merge = merge;
            this->_get_lazy = get_lazy;
            this->ds = std::vector<T>(2 * size - 1);
        }

    public:
        std::vector<T> ds;

        SegmentTree(
            int size,
            std::function<void(T &, U &)> update,
            std::function<T(T &, T &)> merge = [](T &l, T &r) { return l + r; },
            std::function<optional<U>(T &)> get_lazy = [](T &value) { return optional<U>(); })
        {
            init(size, update, merge, get_lazy);
        }

        void build(std::function<T(int)> builder)
        {
            build(0, 0, size, builder);
        }

        void update(int x, U upd)
        {
            update(0, 0, size, x, x + 1, upd);
        }

        void update(int x, int y, U upd)
        {
            update(0, 0, size, x, y, upd);
        }

        T query(int x, int y)
        {
            return query(0, 0, size, x, y);
        }
    };
} // namespace asl

#include <tuple>

#include <random>

#include <utility>

using namespace std;
using namespace asl;

vector<int> xrank;

struct state
{
    int value, left, right, max_diff, index, lazy;
};

void init(int k, vector<int> r)
{
    int n = r.size();
    xrank.resize(n);

    SegmentTree<state, int> st(
        n, [&](state &s, int &u) { s.value += u; s.lazy += u; },
        [&](state &l, state &r) { state res;
        if (l.value < r.value) {
            res = l;
            res.lazy = 0;
        } else if (r.value < l.value) {
            res = r;
            res.lazy = 0;
        } else {
            res.value = l.value;
            res.left = l.left;
            res.right = r.right;
            res.max_diff = max({l.max_diff, r.max_diff, r.left - l.right});
            res.lazy = 0;

            if (l.max_diff == res.max_diff) {
                res.index = l.index;
            } else if (r.max_diff == res.max_diff) {
                res.index = r.index;
            } else {
                res.index = r.left;
            }
        }
        return res; },
        [&](state &s) {
            if (s.lazy) {
                int value = s.lazy;
                s.lazy = 0;
                return optional<int>(value);
            } else {
                return optional<int>();
            } });

    st.build([&](int p) {
        state res = {r[p], p, p, 0, p, 0};
        return res;
    });

    for (int i = 0; i < n; ++i)
    {
        auto res = st.query(0, n);
        int wrap_diff = res.left + n - res.right;
        int index = res.index;
        if (wrap_diff > res.max_diff)
            index = res.left;

        xrank[index] = n - i;

        st.update(index, +1e6);

        if (index >= k - 1)
            st.update(index - k + 1, index, -1);
        else
        {
            if (index)
                st.update(0, index, -1);
            st.update(n + index - (k - 1), n, -1);
        }
    }
}

int compare_plants(int a, int b)
{
    return xrank[a] > xrank[b] ? +1 : -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25