Submission #1258184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258184		uranium235	Election (BOI18_election)	Java	0 / 100	87 ms	14416 KiB

election

//package ojuz;

import java.io.*;
import java.util.*;
import java.util.function.IntBinaryOperator;

public class election {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(reader.readLine());
        BitSet votes = new BitSet(n);
        for (int i = 0; i < n; i++) votes.set(i, reader.read() == 'C');
        reader.read();
        n++;
        int[] pref = new int[n];
        pref[0] = 0;
        for (int i = 1; i < n; i++) pref[i] = pref[i - 1] + (votes.get(i - 1) ? 1 : -1);
        SegTree tree = new SegTree(n, pref);

        int log = 31 - Integer.numberOfLeadingZeros(n) + 1;
        int[][] sparse = new int[log][n];
        System.arraycopy(pref, 0, sparse[0], 0, n);
        for (int i = 1; i < log; i++) for (int j = 0; j < n; j++) sparse[i][j] = Math.min(sparse[i - 1][j], sparse[i - 1][Math.min(n - 1, j + (1 << (i - 1)))]);

        IntBinaryOperator rmq = (l, r) -> {
            int min = Integer.MAX_VALUE;
            for (int i = log - 1; i >= 0; i--) if (l + (1 << i) < r) {
                min = Math.min(min, sparse[i][l + (1 << i)]);
                l += (1 << i);
            }
            return min;
        };

        int q = Integer.parseInt(reader.readLine());
        for (int i = 0; i < q; i++) {
            String[] query = reader.readLine().split(" ");
            int l = Integer.parseInt(query[0]) - 1, r = Integer.parseInt(query[1]);
            Node max = tree.query(l, r, 0, n - 1, 1);
            int diff = max.val - pref[r];
            int min = Math.min(rmq.applyAsInt(l, max.idx) - pref[l], rmq.applyAsInt(max.idx, r) - pref[l] + diff);
            writer.write(String.valueOf(diff + Math.max(0, -min)));
            writer.newLine();
        }

        writer.flush();
    }

    static class SegTree {
        public final Node[] a;
        public final int[] pref;
        public final int n;
        public SegTree(int n, int[] pref) {
            this.a = new Node[4 * n];
            this.pref = pref;
            this.n = n;
            build(0, n - 1, 1);
        }

        public void build(int l, int r, int v) {
            a[v] = new Node();
            if (l == r) {
                a[v].idx = l;
                a[v].val = pref[l];
            } else {
                int m = (l + r) / 2;
                build(l, m, 2 * v);
                build(m + 1, r, 2 * v + 1);
                a[v].merge(a[2 * v], a[2 * v + 1]);
            }
        }

        public Node query(int a, int b, int l, int r, int v) {
            if (r < a || l > b) return new Node(-1, Integer.MIN_VALUE);
            if (a <= l && r <= b) return this.a[v];
            int m = (l + r) / 2;
            return new Node().merge(query(a, b, l, m, 2 * v), query(a, b, m + 1, r, 2 * v + 1));
        }
    }

    static class Node {
        public int idx, val;
        public Node() {}
        public Node(int idx, int val) {
            this.idx = idx;
            this.val = val;
        }
        public Node merge(Node l, Node r) {
            val = Math.max(l.val, r.val);
            idx = l.val > r.val ? l.idx : r.idx;
            return this;
        }
    }
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18