oj.uz

Submission #302557

# Submission time Handle Problem Language Result Execution time Memory
302557 2020-09-18T19:13:18 Z polyakoff Comparing Plants (IOI20_plants) Java 11
14 / 100
 4000 ms 331372 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10480 KB Output is correct
2 Correct 78 ms 10216 KB Output is correct
3 Correct 82 ms 10344 KB Output is correct
4 Incorrect 82 ms 10560 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 78 ms 10468 KB Output is correct
2 Correct 79 ms 10356 KB Output is correct
3 Correct 79 ms 10232 KB Output is correct
4 Correct 80 ms 10344 KB Output is correct
5 Correct 93 ms 10996 KB Output is correct
6 Correct 181 ms 19452 KB Output is correct
7 Correct 637 ms 63124 KB Output is correct
8 Correct 118 ms 11620 KB Output is correct
9 Correct 195 ms 21764 KB Output is correct
10 Correct 697 ms 67940 KB Output is correct
11 Correct 698 ms 66108 KB Output is correct
12 Correct 616 ms 62156 KB Output is correct
13 Correct 798 ms 63448 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10468 KB Output is correct
2 Correct 79 ms 10356 KB Output is correct
3 Correct 79 ms 10232 KB Output is correct
4 Correct 80 ms 10344 KB Output is correct
5 Correct 93 ms 10996 KB Output is correct
6 Correct 181 ms 19452 KB Output is correct
7 Correct 637 ms 63124 KB Output is correct
8 Correct 118 ms 11620 KB Output is correct
9 Correct 195 ms 21764 KB Output is correct
10 Correct 697 ms 67940 KB Output is correct
11 Correct 698 ms 66108 KB Output is correct
12 Correct 616 ms 62156 KB Output is correct
13 Correct 798 ms 63448 KB Output is correct
14 Correct 1389 ms 100788 KB Output is correct
15 Execution timed out 4239 ms 331372 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 10352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10232 KB Output is correct
2 Correct 83 ms 10468 KB Output is correct
3 Incorrect 86 ms 10108 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10112 KB Output is correct
2 Correct 78 ms 10488 KB Output is correct
3 Incorrect 83 ms 10296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10480 KB Output is correct
2 Correct 78 ms 10216 KB Output is correct
3 Correct 82 ms 10344 KB Output is correct
4 Incorrect 82 ms 10560 KB Output isn't correct
5 Halted 0 ms 0 KB -