oj.uz

Submission #300289

# Submission time Handle Problem Language Result Execution time Memory
300289 2020-09-17T04:23:54 Z marX Comparing Plants (IOI20_plants) C++17
44 / 100
 673 ms 14584 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 74 ms 3212 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 73 ms 3340 KB Output is correct
11 Correct 85 ms 3340 KB Output is correct
12 Correct 76 ms 3340 KB Output is correct
13 Correct 74 ms 3216 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 74 ms 3212 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 73 ms 3340 KB Output is correct
11 Correct 85 ms 3340 KB Output is correct
12 Correct 76 ms 3340 KB Output is correct
13 Correct 74 ms 3216 KB Output is correct
14 Correct 107 ms 3832 KB Output is correct
15 Correct 667 ms 14456 KB Output is correct
16 Correct 109 ms 3908 KB Output is correct
17 Correct 673 ms 14484 KB Output is correct
18 Correct 392 ms 14484 KB Output is correct
19 Correct 400 ms 14456 KB Output is correct
20 Correct 589 ms 14456 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 69 ms 3320 KB Output is correct
4 Correct 320 ms 14456 KB Output is correct
5 Correct 390 ms 14456 KB Output is correct
6 Correct 539 ms 14476 KB Output is correct
7 Correct 634 ms 14484 KB Output is correct
8 Correct 666 ms 14584 KB Output is correct
9 Correct 346 ms 14456 KB Output is correct
10 Correct 349 ms 14584 KB Output is correct
11 Correct 291 ms 14584 KB Output is correct
12 Correct 330 ms 14456 KB Output is correct
13 Correct 392 ms 14480 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -