Submission #634073

#	Time	Username	Problem	Language	Result	Execution time	Memory
634073		Flbs	Election (BOI18_election)	Java	0 / 100	146 ms	12632 KiB

election

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

class Election {
    private static int n, q;
    private static String votes;
    private static ArrayList<ArrayList<Integer[]>> queries;

    public static void main(String[] args) {
        readData();
        solve();
    }
    
    public static void readData() {
        queries = new ArrayList<>();

        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        scanner.nextLine();
        votes = scanner.nextLine();
        q = scanner.nextInt();

        for (int i = 0; i < n; i++) {
            queries.add(new ArrayList<>());
        }

        for (int i = 0; i < q; i++) {
            int x = scanner.nextInt() - 1;
            int y = scanner.nextInt() - 1;

            queries.get(x).add(new Integer[]{y, i});
        }

        scanner.close();
    }

    public static void solve() {
        SegmentTree sTree = new SegmentTree(n);

        ArrayList<Integer> eliminatedList = new ArrayList<>();
        ArrayList<Integer> result = new ArrayList<>(Collections.nCopies(q, 0));
        for (int i = n - 1; i >= 0; i--) {
            if (votes.charAt(i) == 'C') {
                // we can un-eliminate a T (left-right parsing will be ok). We choose the closest one to i,
                // since it's most optimal this way for the right to left parsing (more C's appear in front of it)
                
                sTree.update(1, 0, n - 1, i, 1);
                if (!eliminatedList.isEmpty()) {
                    var element = eliminatedList.get(eliminatedList.size() - 1);
                    eliminatedList.remove(eliminatedList.size() - 1);

                    sTree.update(1, 0, n - 1, element, -1);
                }
            }
            else {
                // it's a T at the begining of the sequence so it breaks it when parsing from left to right
                eliminatedList.add(i);
            }

            for (Integer[] qry: queries.get(i)) {
                int leftToRigthCost = eliminatedList.size() - binarySearch(eliminatedList, qry[0]) - 1;
                int rigthToLeftCost = Math.max(0, -sTree.getMinSuffixSumInInterval(1, 0, n - 1, i, qry[0])[1]);
                result.set(qry[1], leftToRigthCost + rigthToLeftCost);
            }
        }

        for (int i = 0; i < q; i++) {
            System.out.println(result.get(i));
        }
    }

    public static int binarySearch(ArrayList<Integer> list, int value) {
        int res = -1;
        for (int i = 18; i >= 0; i--) {
            if (res + (1<<i) < list.size() && list.get(res + (1<<i)) > value) {
                res += (1<<i);
            }
        }

        return res;
    }
}

class SegmentTree {
    private ArrayList<Integer> sum;
    private ArrayList<Integer> minSuffix;

    public SegmentTree(int size) {
        sum = new ArrayList<>(Collections.nCopies(size * 4, 0));
        minSuffix = new ArrayList<>(Collections.nCopies(size * 4, 0));
    }

    void update(int node, int left, int right, int pos, int value) {
        if (left == right) {
            sum.set(node, value);
            return;
        }

        int mid = (left + right)/2;

        if (pos <= mid) {
            update(2*node, left, mid, pos, value);
        }
        else {
            update(2*node + 1, mid + 1, right, pos, value);
        }

        sum.set(node, sum.get(2*node) + sum.get(2*node + 1));
        minSuffix.set(node, Math.min(minSuffix.get(2*node) + sum.get(2*node + 1), minSuffix.get(2*node + 1)));
    }

    int[] getMinSuffixSumInInterval(int node, int left, int right, int leftQuery, int rightQuery) {
        if (leftQuery <= left && right <= rightQuery) {
            return new int[]{sum.get(node), minSuffix.get(node)};
        }

        int mid = (left + right)/2;

        int minSuffixRes = 0;
        int sumRes = 0;
        if (leftQuery <= mid) {
            var ret = getMinSuffixSumInInterval(2*node, left, mid, leftQuery, rightQuery);
            sumRes = ret[0];
            minSuffixRes = ret[1];
        }
        if(rightQuery > mid) {
            var ret = getMinSuffixSumInInterval(2*node + 1, mid + 1, right, leftQuery, rightQuery);
            sumRes = sumRes + ret[0];
            minSuffixRes = Math.min(minSuffixRes + ret[0], ret[1]);
        }

        return new int[]{sumRes, minSuffixRes};
    }
}

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