Submission #302557

#	Time	Username	Problem	Language	Result	Execution time	Memory
302557		polyakoff	Comparing Plants (IOI20_plants)	Java	14 / 100	4239 ms	331372 KiB

plants

import java.util.ArrayList;

class plants {
    private int k, n;
    private int[] r, level;

    private class SegTree {
        class Node {
            int min, toAdd;
            ArrayList<Integer> inds;

            Node() {
                toAdd = 0;
                inds = new ArrayList<>();
            }
        }
        Node[] t;
        int size;

        Node merge(Node t1, Node t2) {
            Node res = new Node();
            if (t1.min < t2.min) {
                res.min = t1.min;
                res.inds.addAll(t1.inds);
            } else if (t2.min < t1.min) {
                res.min = t2.min;
                res.inds.addAll(t2.inds);
            } else {
                res.min = t1.min;
                res.inds.addAll(t1.inds);
                if (res.inds.size() > 0 && t2.inds.size() > 0 && t2.inds.get(0) - res.inds.get(res.inds.size() - 1) < k) {
                    for (int i = 1; i < t2.inds.size(); i++)
                        res.inds.add(t2.inds.get(i));
                } else {
                    res.inds.addAll(t2.inds);
                }
            }
            return res;
        }
        void push(int v) {
            if (t[v].toAdd != 0) {
                t[v * 2 + 1].min += t[v].toAdd;
                t[v * 2 + 1].toAdd += t[v].toAdd;
                t[v * 2 + 2].min += t[v].toAdd;
                t[v * 2 + 2].toAdd += t[v].toAdd;
                t[v].toAdd = 0;
            }
        }
        void build(int v, int tl, int tr, int[] arr) {
            if (tl == tr) {
                t[v] = new Node();
                t[v].min = arr[tl];
                t[v].inds.add(tl);
            } else {
                int tm = (tl + tr) / 2;
                build(v * 2 + 1, tl, tm, arr);
                build(v * 2 + 2, tm + 1, tr, arr);
                t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
            }
        }
        void addOn(int v, int tl, int tr, int l, int r, int val) {
            if (r < tl || tr < l)
                return;
            if (l <= tl && tr <= r) {
                t[v].min += val;
                t[v].toAdd += val;
                return;
            }
            int tm = (tl + tr) / 2;
            push(v);
            addOn(v * 2 + 1, tl, tm, l, r, val);
            addOn(v * 2 + 2, tm + 1, tr, l, r, val);
            t[v] = merge(t[v * 2 + 1], t[v * 2 + 2]);
        }

        void build(int[] arr) {
            size = arr.length;
            t = new Node[size * 4];
            build(0, 0, size - 1, arr);
        }
        void addOn(int l, int r, int val) {
            addOn(0, 0, size - 1, l, r, val);
        }
        ArrayList<Integer> findZeros() {
            ArrayList<Integer> res = new ArrayList<>();
            if (t[0].inds.size() >= 2 && t[0].inds.get(0) + n - t[0].inds.get(t[0].inds.size() - 1) < k) {
                for (int i = 1; i < t[0].inds.size(); i++)
                    res.add(t[0].inds.get(i));
            } else {
                res.addAll(t[0].inds);
            }
            return res;
        }
    }

    void init(int k, int[] r) {
        this.k = k;
        this.r = r;
        n = r.length;

        SegTree st = new SegTree();
        st.build(r);

        level = new int[n];
        for (int cnt = 0, lvl = 0; cnt < n; lvl++) {
            ArrayList<Integer> zeros = st.findZeros();
            for (int i : zeros) {
                level[i] = lvl;
                st.addOn(i, i, k - 1);
                st.addOn(Math.max(0, i - (k - 1)), i - 1, -1);
                if (i - (k - 1) < 0)
                    st.addOn(n - (k - 1 - i), n - 1, -1);
            }
            cnt += zeros.size();
//            System.out.println(cnt);
        }

    }

    int compare_plants(int x, int y) {
        if (level[x] < level[y])
            return 1;
        else if (level[x] > level[y])
            return -1;
        return 0;
    }
}

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