Submission #303224

#	Time	Username	Problem	Language	Result	Execution time	Memory
303224		llaki	Comparing Plants (IOI20_plants)	Java	0 / 100	93 ms	10396 KiB

plants

import java.util.Arrays;

public class plants {
    int n;
    int[] nxt;
    int[] r;

    void init(int k, int[] r) {
        n = r.length;
        nxt = new int[n];
        this.r = r;
        // r[i] = (a[i] > a[(i + 1)%n] ? 1 : 0)
        // x -> find smallest z on circle clockwise s.t. r[z] != r[x].
        // If y is between x and z (clockwise), than ans(x,y) = r[x].

        // r[x] = r[x+1] = ... = r[s] = 1 => a[x] > a[x+1] > a[x+2] > ... > a[s + 1]
        // r[x] = r[x+1] = ... = r[s] = -1 => a[x] < a[x+1] < a[x+2] > ... < a[s + 1]
        // nxt[x] = smallest y s.t. nxt[y] != nxt[x]. for query z s.t. x < z <= nxt[x] + 1, comp(x,z) known.
        for (int i = 0; i < n; i++) {
            int j = i;
            boolean jump = false;
            while (r[(j + 1) % n] == r[i]) {
                j = (j + 1) % n;
                if (j == 0) jump = true;
            }
            // r[i] = r[i+1] = ... = r[j] != r[j + 1].
            for (int x = i; x <= j; x++) {
                nxt[x] = j + 1;
            }
            if (jump) break;
            i = j;
        }
        //System.out.println(Arrays.toString(nxt));
    }

    boolean between(int l, int r, int x) {
        if (l <= r) {
            return l <= x && x <= r;
        }
        return (r <= x && x <= n - 1) || (0 <= x && x <= l);
    }

    int compare_plants(int x, int y) {
        // r[x] > r[x+1] > ... > r[j].
        if (between(x, nxt[x], y)) {
            return r[x] > 0 ? 1 : -1;
        }
        if (between(y, nxt[y], x)) {
            return r[y] > 0 ? -1 : 1;
        }
        return 0;
    }
}

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