oj.uz

Submission #302574

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

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, first, last;
            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);
                res.first = t1.first;
                res.last = t1.last;
            } else if (t2.min < t1.min) {
                res.min = t2.min;
                res.inds.addAll(t2.inds);
                res.first = t2.first;
                res.last = t2.last;
            } else {
                res.min = t1.min;
                res.inds.addAll(t1.inds);
                if (t2.first - t1.last < k) {
                    for (int i = 1; i < t2.inds.size(); i++)
                        res.inds.add(t2.inds.get(i));
                } else {
                    res.inds.addAll(t2.inds);
                }
                res.first = t1.first;
                res.last = t2.last;
            }
            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);
                t[v].first = t[v].last = 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].first != t[0].last && t[0].first + n - t[0].last < 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) {
//                System.out.print(i + " ");
                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);
            }
//            System.out.println();
            cnt += zeros.size();
        }

//        System.out.println(Arrays.toString(level));

    }

    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 77 ms 10348 KB Output is correct
2 Correct 80 ms 10472 KB Output is correct
3 Correct 78 ms 10344 KB Output is correct
4 Incorrect 76 ms 10364 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 79 ms 10340 KB Output is correct
2 Correct 82 ms 10340 KB Output is correct
3 Correct 82 ms 10244 KB Output is correct
4 Correct 80 ms 10340 KB Output is correct
5 Correct 94 ms 10616 KB Output is correct
6 Correct 166 ms 19432 KB Output is correct
7 Correct 658 ms 63028 KB Output is correct
8 Correct 126 ms 11828 KB Output is correct
9 Correct 195 ms 20752 KB Output is correct
10 Correct 679 ms 69248 KB Output is correct
11 Correct 625 ms 62656 KB Output is correct
12 Correct 589 ms 61432 KB Output is correct
13 Correct 602 ms 63944 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10340 KB Output is correct
2 Correct 82 ms 10340 KB Output is correct
3 Correct 82 ms 10244 KB Output is correct
4 Correct 80 ms 10340 KB Output is correct
5 Correct 94 ms 10616 KB Output is correct
6 Correct 166 ms 19432 KB Output is correct
7 Correct 658 ms 63028 KB Output is correct
8 Correct 126 ms 11828 KB Output is correct
9 Correct 195 ms 20752 KB Output is correct
10 Correct 679 ms 69248 KB Output is correct
11 Correct 625 ms 62656 KB Output is correct
12 Correct 589 ms 61432 KB Output is correct
13 Correct 602 ms 63944 KB Output is correct
14 Correct 1177 ms 109868 KB Output is correct
15 Execution timed out 4058 ms 280312 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10344 KB Output is correct
2 Correct 80 ms 10484 KB Output is correct
3 Correct 454 ms 41044 KB Output is correct
4 Execution timed out 4082 ms 279096 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 10484 KB Output is correct
2 Correct 81 ms 10612 KB Output is correct
3 Incorrect 79 ms 10492 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 10104 KB Output is correct
2 Correct 80 ms 10464 KB Output is correct
3 Incorrect 84 ms 10240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 10348 KB Output is correct
2 Correct 80 ms 10472 KB Output is correct
3 Correct 78 ms 10344 KB Output is correct
4 Incorrect 76 ms 10364 KB Output isn't correct
5 Halted 0 ms 0 KB -