Submission #302556

# Submission time Handle Problem Language Result Execution time Memory
302556 2020-09-18T19:12:45 Z polyakoff Comparing Plants (IOI20_plants) Java 11
Compilation error
0 ms 0 KB
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();
        }

    }

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

Compilation message

plants.java:82: error: cannot find symbol
        ArrayList<Integer> findZeros() {
        ^
  symbol:   class ArrayList
  location: class plants.SegTree
plants.java:8: error: cannot find symbol
            ArrayList<Integer> inds;
            ^
  symbol:   class ArrayList
  location: class plants.SegTree.Node
plants.java:12: error: cannot find symbol
                inds = new ArrayList<>();
                           ^
  symbol:   class ArrayList
  location: class plants.SegTree.Node
plants.java:83: error: cannot find symbol
            ArrayList<Integer> res = new ArrayList<>();
            ^
  symbol:   class ArrayList
  location: class plants.SegTree
plants.java:83: error: cannot find symbol
            ArrayList<Integer> res = new ArrayList<>();
                                         ^
  symbol:   class ArrayList
  location: class plants.SegTree
plants.java:104: error: cannot find symbol
            ArrayList<Integer> zeros = st.findZeros();
            ^
  symbol:   class ArrayList
  location: class plants
6 errors