Submission #3068900


Source Code Expand

// package other2015.utpc2014;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    static long __startTime = System.currentTimeMillis();

    static class BoardSet {
        List<Integer> positionList;
        Map<Integer,Integer> positionMapper;

        TreeSet<Long> colorByPosition;
        TreeSet<Long> positionByColor;

        SegmentTreePURMQ minColorPositions;
        int leftMostColor;
        int leftMostPosition;

        static final int MASK = (1<<20)-1;
        static final int COLOR_SIZE = 200010;

        BoardSet(Set<Integer> set, boolean rev) {
            positionList = new ArrayList<>(set);
            Collections.sort(positionList);
            if (rev) {
                Collections.reverse(positionList);
            }
            positionMapper = new HashMap<>();
            for (int i = 0 ; i < positionList.size() ; i++) {
                positionMapper.put(positionList.get(i), i);
            }

            colorByPosition = new TreeSet<>();
            positionByColor = new TreeSet<>();

            long[] data = new long[COLOR_SIZE];
            Arrays.fill(data, MASK+10);
            minColorPositions = new SegmentTreePURMQ(data);
            leftMostColor = leftMostPosition = -1;
        }

        long findPositionAt(int index) {
            if (index < 0 || index > positionList.size()) {
                throw new RuntimeException("position id overflow");
            }
            if (index == positionList.size()) {
                return 0;
            }
            return Math.abs(positionList.get(index));
        }

        long findLeftMostPosition() {
            int idx = (int)(colorByPosition.first()>>20);
            return findPositionAt(idx);
        }

        long findLeftMostPositionOnColor() {
            return findPositionAt(leftMostPosition);
        }

        int findMinimumPositionIndex(int color) {
            long colorMin = ((long)color)<<20;
            Long best = positionByColor.ceiling(colorMin);
            if (best == null || (best >> 20) != color) {
                return 1<<20; // not found
            }
            return (int)(best & MASK);
        }


        void addBoard(int x, int color) {
            long positionIdx = positionMapper.get(x);
            long byPosition = (positionIdx<<20) + color;
            colorByPosition.add(byPosition);

            long byColor = (((long)color)<<20) + positionIdx;
            positionByColor.add(byColor);

            updateOnColor(color);
            updateMinimum();
        }

        void removeBoard(int x, int color) {
            long positionIdx = positionMapper.get(x);
            long byPosition = (positionIdx<<20) + color;
            colorByPosition.remove(byPosition);

            long byColor = (((long)color)<<20) + positionIdx;
            positionByColor.remove(byColor);

            updateOnColor(color);
            updateMinimum();
        }

        void updateOnColor(int color) {
            int idx = findMinimumPositionIndex(color);
            minColorPositions.update(color, idx);
        }

        void updateMinimum() {
            if (colorByPosition.size() == 0) {
                leftMostColor = -1;
                leftMostPosition = -1;
                return;
            }
            long leftMost = colorByPosition.first();
            leftMostColor = (int)(leftMost&MASK);

            long minPosition = minimumPositionExcept(leftMostColor);
            if (minPosition >= MASK) {
                leftMostPosition = positionList.size(); // zero
            } else {
                leftMostPosition = (int)minPosition;
            }
        }

        long minimumPositionExcept(int color) {
            // [0, color) & [color+1, MAX)
            return Math.min(minColorPositions.min(1, color), minColorPositions.min(color+1, COLOR_SIZE-1));
        }
    }


    public static void main(String[] args) {
        colorCounter = new FenwickTree(BoardSet.COLOR_SIZE);
        colorPositionSum = new FenwickTree(BoardSet.COLOR_SIZE);

        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int[][] initial = new int[n][2];
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < 2 ; j++) {
                initial[i][j] = in.nextInt();
            }
        }
        int q = in.nextInt();
        int[][] queries = new int[q][3];
        for (int i = 0; i < q ; i++) {
            for (int j = 0; j < 3 ; j++) {
                queries[i][j] = in.nextInt();
            }
        }

        debug(initial, queries);

        Set<Integer> plusPosition = new HashSet<>();
        Set<Integer> minusPosition = new HashSet<>();
        for (int i = 0; i < n ; i++) {
            if (initial[i][0] >= 0) {
                plusPosition.add(initial[i][0]);
            } else {
                minusPosition.add(initial[i][0]);
            }
        }
        for (int i = 0; i < q ; i++) {
            if (queries[i][1] >= 0) {
                plusPosition.add(queries[i][1]);
            } else {
                minusPosition.add(queries[i][1]);
            }
        }


        BoardSet plus = new BoardSet(plusPosition, true);
        BoardSet minus = new BoardSet(minusPosition, false);
        for (int i = 0; i < n ; i++) {
            if (initial[i][0] >= 0) {
                plus.addBoard(initial[i][0], initial[i][1]);
            } else {
                minus.addBoard(initial[i][0], initial[i][1]);
            }
            colorCounter.add(initial[i][1], 1);
            colorPositionSum.add(initial[i][1], initial[i][1]);
        }

        debug("added initial");

        for (int i = 0; i < q ; i++) {
            if (queries[i][0] == 1) {
                if (queries[i][1] >= 0) {
                    plus.addBoard(queries[i][1], queries[i][2]);
                } else {
                    minus.addBoard(queries[i][1], queries[i][2]);
                }
                colorCounter.add(queries[i][2], 1);
                colorPositionSum.add(queries[i][2], queries[i][2]);
            } else {
                if (queries[i][1] >= 0) {
                    plus.removeBoard(queries[i][1], queries[i][2]);
                } else {
                    minus.removeBoard(queries[i][1], queries[i][2]);
                }
                colorCounter.add(queries[i][2], -1);
                colorPositionSum.add(queries[i][2], -queries[i][2]);
            }

            long best = Long.MAX_VALUE;

            int centerColor = findCenterColor();
            debug("center", i, centerColor);
            long ccost = colorCost(centerColor);

            if (minus.leftMostColor == -1) {
                debug("only on plus", i, plus.leftMostColor, plus.leftMostPosition, colorCost(plus.leftMostColor));

                // only on plus
                best = Math.min(best, colorCost(plus.leftMostColor) + plus.findLeftMostPositionOnColor());
                best = Math.min(best, ccost + plus.findLeftMostPosition());
            } else if (plus.leftMostColor == -1) {
                debug("only on minus", i, minus.leftMostColor, minus.leftMostPosition);

                // only on minus
                best = Math.min(best, colorCost(minus.leftMostColor) + minus.findLeftMostPositionOnColor());
                best = Math.min(best, ccost + minus.findLeftMostPosition());
            } else {
                debug("we have both", i, minus.leftMostColor, minus.leftMostPosition, plus.leftMostColor, plus.leftMostPosition);

                // use center color
                long minLeft = minus.findLeftMostPosition();
                long maxRight = plus.findLeftMostPosition();
                best = Math.min(best, ccost + minLeft * 2 + maxRight);
                best = Math.min(best, ccost + maxRight * 2 + minLeft);

                long lccost = colorCost(minus.leftMostColor);
                long rccost = colorCost(plus.leftMostColor);
                long ml = minus.findLeftMostPositionOnColor();
                long mr = plus.findLeftMostPositionOnColor();
                if (plus.leftMostColor == minus.leftMostColor) {
                    best = Math.min(best, lccost+ml*2+mr);
                    best = Math.min(best, rccost+mr*2+ml);
                } else {
                    best = Math.min(best, lccost+ml*2+maxRight);
                    best = Math.min(best, lccost+maxRight*2+ml);
                    best = Math.min(best, rccost+mr*2+minLeft);
                    best = Math.min(best, rccost+minLeft*2+mr);
                }
            }
            out.println(best);
        }



        out.flush();
    }

    static FenwickTree colorCounter;
    static FenwickTree colorPositionSum;
    static long colorCost(int color) {
        long leftCnt = colorCounter.range(1, color-1);
        long leftPos = colorPositionSum.range(1, color-1);

        long rightCnt = colorCounter.range(color+1, BoardSet.COLOR_SIZE-1);
        long rightPos = colorPositionSum.range(color+1, BoardSet.COLOR_SIZE-1);
        return (leftCnt*color-leftPos)+(rightPos-rightCnt*color);
    }

    static int findCenterColor() {
        int total = (int)(colorCounter.range(1, BoardSet.COLOR_SIZE-1));
        int find = (total + 1) / 2;
        int l = 0;
        int r = BoardSet.COLOR_SIZE-1;

        while (r - l > 1) {
            int med =  (l + r) / 2;
            int subsum = (int)(colorCounter.range(1, med));
            if (subsum < find) {
                l = med;
            } else {
                r = med;
            }
        }
        return r;
    }


    public static class FenwickTree {
        long N;
        long[] data;

        public FenwickTree(int n) {
            N = n;
            data = new long[n + 1];
        }

        /**
         * Computes value of [1, i].
         * <p>
         * O(logn)
         *
         * @param i
         * @return
         */
        public long sum(int i) {
            long s = 0;
            while (i > 0) {
                s += data[i];
                i -= i & (-i);
            }
            return s;
        }

        /**
         * Computes value of [i, j].
         * <p>
         * O(logn)
         *
         * @param i
         * @param j
         * @return
         */
        public long range(int i, int j) {
            if (i <= j) {
                return sum(j) - sum(i - 1);
            } else {
                return 0;
            }
        }

        /**
         * Sets value x into i-th position.
         * <p>
         * O(logn)
         *
         * @param i
         * @param x
         */
        public void set(int i, long x) {
            add(i, x - range(i, i));
        }

        /**
         * Adds value x into i-th position.
         * <p>
         * O(logn)
         *
         * @param i
         * @param x
         */
        public void add(int i, long x) {
            while (i <= N) {
                data[i] += x;
                i += i & (-i);
            }
        }
    }

    /**
     * Segment tree (point update, range minimum query)
     */
    public static class SegmentTreePURMQ {
        int N;
        int M;
        long[] seg;

        public SegmentTreePURMQ(long[] data) {
            N = Integer.highestOneBit(data.length-1)<<2;
            M = (N >> 1) - 1;

            seg = new long[N];
            Arrays.fill(seg, Integer.MAX_VALUE);
            for (int i = 0 ; i < data.length ; i++) {
                seg[M+i] = data[i];
            }
            for (int i = M-1 ; i >= 0 ; i--) {
                seg[i] = compute(i);
            }
        }

        /**
         * Uodates value at position minIndexSum.
         *
         * @param idx
         * @param value
         */
        public void update(int idx, int value) {
            seg[M+idx] = value;
            int i = M+idx;
            while (true) {
                i = (i-1) >> 1;
                seg[i] = compute(i);
                if (i == 0) {
                    break;
                }
            }
        }

        private long compute(int i) {
            return Math.min(seg[i*2+1], seg[i*2+2]);
        }

        /**
         * Finds minimum value from range [l,r).
         *
         * @param l
         * @param r
         * @return minimum value
         */
        public long min(int l, int r) {
            return min(l, r, 0, 0, M+1);
        }

        private long min(int l, int r, int idx, int fr, int to) {
            if (to <= l || r <= fr) {
                return Integer.MAX_VALUE;
            }
            if (l <= fr && to <= r) {
                return seg[idx];
            }

            int med = (fr+to) / 2;
            long ret = Integer.MAX_VALUE;
            ret = Math.min(ret, min(l, r, idx*2+1, fr, med));
            ret = Math.min(ret, min(l, r, idx*2+2, med, to));
            return ret;
        }
    }

    private static void printTime(String label) {
        debug(label, System.currentTimeMillis() - __startTime);
    }

    public static void debug(Object... o) {

        // System.err.println(Arrays.deepToString(o));
    }

    public static class InputReader {
        private static final int BUFFER_LENGTH = 1 << 12;
        private InputStream stream;
        private byte[] buf = new byte[BUFFER_LENGTH];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int next() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            return (char) skipWhileSpace();
        }

        public String nextToken() {
            int c = skipWhileSpace();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            int c = skipWhileSpace();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = next();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        int skipWhileSpace() {
            int c = next();
            while (isSpaceChar(c)) {
                c = next();
            }
            return c;
        }

        boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}

Submission Info

Submission Time
Task J - 看板の塗り替え
User hamadu
Language Java8 (OpenJDK 1.8.0)
Score 300
Code Size 15944 Byte
Status AC
Exec Time 1557 ms
Memory 132236 KB

Judge Result

Set Name Subtask All
Score / Max Score 30 / 30 270 / 270
Status
AC × 26
AC × 53
Set Name Test Cases
Subtask subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt, subtask_20.txt, subtask_21.txt, subtask_22.txt, subtask_23.txt, subtask_24.txt, subtask_25.txt
All scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt, subtask_20.txt, subtask_21.txt, subtask_22.txt, subtask_23.txt, subtask_24.txt, subtask_25.txt
Case Name Status Exec Time Memory
scrambled_00.txt AC 98 ms 44756 KB
scrambled_01.txt AC 1552 ms 132236 KB
scrambled_02.txt AC 1169 ms 109912 KB
scrambled_03.txt AC 776 ms 78152 KB
scrambled_04.txt AC 638 ms 64724 KB
scrambled_05.txt AC 682 ms 69084 KB
scrambled_06.txt AC 1344 ms 107148 KB
scrambled_07.txt AC 395 ms 58572 KB
scrambled_08.txt AC 1189 ms 105128 KB
scrambled_09.txt AC 1111 ms 87812 KB
scrambled_10.txt AC 427 ms 51980 KB
scrambled_11.txt AC 1532 ms 127300 KB
scrambled_12.txt AC 1037 ms 109260 KB
scrambled_13.txt AC 655 ms 67184 KB
scrambled_14.txt AC 926 ms 94228 KB
scrambled_15.txt AC 835 ms 76148 KB
scrambled_16.txt AC 1455 ms 117024 KB
scrambled_17.txt AC 821 ms 76824 KB
scrambled_18.txt AC 519 ms 64300 KB
scrambled_19.txt AC 1334 ms 92808 KB
scrambled_20.txt AC 584 ms 63468 KB
scrambled_21.txt AC 1557 ms 125336 KB
scrambled_22.txt AC 1490 ms 119100 KB
scrambled_23.txt AC 670 ms 72948 KB
scrambled_24.txt AC 1544 ms 118676 KB
scrambled_25.txt AC 848 ms 78264 KB
scrambled_26.txt AC 1145 ms 80080 KB
subtask_00.txt AC 183 ms 45140 KB
subtask_01.txt AC 194 ms 45396 KB
subtask_02.txt AC 185 ms 45000 KB
subtask_03.txt AC 154 ms 43092 KB
subtask_04.txt AC 154 ms 44884 KB
subtask_05.txt AC 200 ms 45780 KB
subtask_06.txt AC 165 ms 44224 KB
subtask_07.txt AC 191 ms 44372 KB
subtask_08.txt AC 135 ms 46548 KB
subtask_09.txt AC 152 ms 42684 KB
subtask_10.txt AC 201 ms 44096 KB
subtask_11.txt AC 146 ms 44884 KB
subtask_12.txt AC 184 ms 45340 KB
subtask_13.txt AC 139 ms 45900 KB
subtask_14.txt AC 165 ms 44488 KB
subtask_15.txt AC 202 ms 44608 KB
subtask_16.txt AC 181 ms 44104 KB
subtask_17.txt AC 181 ms 45380 KB
subtask_18.txt AC 140 ms 45244 KB
subtask_19.txt AC 200 ms 47048 KB
subtask_20.txt AC 181 ms 45136 KB
subtask_21.txt AC 199 ms 45896 KB
subtask_22.txt AC 170 ms 45512 KB
subtask_23.txt AC 180 ms 45896 KB
subtask_24.txt AC 148 ms 44756 KB
subtask_25.txt AC 188 ms 45384 KB