oj.uz

Submission #302563

# Submission time Handle Problem Language Result Execution time Memory
302563 2020-09-18T19:19:52 Z polyakoff Comparing Plants (IOI20_plants) Java 11
14 / 100
 4000 ms 296924 KB 
import java.util.ArrayList;

class plants {
    private final int oo = (int) (1e9 + 10);
    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 (t1.inds.size() > 0 && t2.inds.size() > 0 && t2.inds.get(0) - t1.inds.get(t1.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, oo);
                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;
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10344 KB Output is correct
2 Correct 77 ms 10232 KB Output is correct
3 Correct 78 ms 10464 KB Output is correct
4 Incorrect 81 ms 10344 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 81 ms 10232 KB Output is correct
2 Correct 79 ms 10384 KB Output is correct
3 Correct 79 ms 10104 KB Output is correct
4 Correct 80 ms 10232 KB Output is correct
5 Correct 98 ms 10744 KB Output is correct
6 Correct 219 ms 22256 KB Output is correct
7 Correct 666 ms 63380 KB Output is correct
8 Correct 122 ms 11640 KB Output is correct
9 Correct 192 ms 21964 KB Output is correct
10 Correct 742 ms 68384 KB Output is correct
11 Correct 591 ms 61196 KB Output is correct
12 Correct 681 ms 66720 KB Output is correct
13 Correct 636 ms 61424 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10232 KB Output is correct
2 Correct 79 ms 10384 KB Output is correct
3 Correct 79 ms 10104 KB Output is correct
4 Correct 80 ms 10232 KB Output is correct
5 Correct 98 ms 10744 KB Output is correct
6 Correct 219 ms 22256 KB Output is correct
7 Correct 666 ms 63380 KB Output is correct
8 Correct 122 ms 11640 KB Output is correct
9 Correct 192 ms 21964 KB Output is correct
10 Correct 742 ms 68384 KB Output is correct
11 Correct 591 ms 61196 KB Output is correct
12 Correct 681 ms 66720 KB Output is correct
13 Correct 636 ms 61424 KB Output is correct
14 Correct 1219 ms 97356 KB Output is correct
15 Execution timed out 4091 ms 296924 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10360 KB Output is correct
2 Correct 80 ms 10380 KB Output is correct
3 Incorrect 488 ms 47928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 10268 KB Output is correct
2 Correct 81 ms 10236 KB Output is correct
3 Incorrect 78 ms 10360 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10472 KB Output is correct
2 Correct 81 ms 10104 KB Output is correct
3 Incorrect 87 ms 10312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10344 KB Output is correct
2 Correct 77 ms 10232 KB Output is correct
3 Correct 78 ms 10464 KB Output is correct
4 Incorrect 81 ms 10344 KB Output isn't correct
5 Halted 0 ms 0 KB -