Submission #2082895

---

Source Code Expand

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.Reader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyInput in = new MyInput(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        public void solve(int testNumber, MyInput in, PrintWriter out) {
            int n = in.nextInt();
            int[] d = in.nextIntArray(n);
//        int m = (int)Math.sqrt(n);
//        Bucket[] bucket = new Bucket[n];
//        for (int i = 0; i < n; i++) {
//            ;
//        }
            SplayTreeIndex tree = new SplayTreeIndex();
            for (int i = 0; i < n; i++) {
                tree.insert(i, d[n - 1 - i]);
            }
            int cnt = 0;
            for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n - i; j++) {
//                dump("dump1", i, j, tree.find(j).value);
//            }

                SplayTreeIndex.Node node = tree.find(0);
//            dump(i, cnt, node.value);
                if (node.value < 0) {
                    cnt++;
                    int idx = SplayTreeIndex.getCount(node.left);
                    tree.add(idx, idx, 1);
                    node = tree.find(0);
                }
                if (node.value < 0 || cnt >= 2) {
                    cnt = 2;
                    break;
                }
                if (i == n - 1) break;

                tree.add(0, node.value, -1);
                tree.remove(0);
                if (node.value == -1 || node.value == n - 2 - i) continue;
//            for (int j = 0; j < n - i - 1; j++) {
//                dump(i, j, tree.find(j).value);
//            }

                int val1 = tree.find(node.value).value;
                int val2 = tree.find(node.value + 1).value;
//            dump(n, i, SplayTreeIndex.getCount(tree.root), node.value, val1, val2);
                if (val1 < val2) {
//                for (int j = 0; j < n - i - 1; j++) {
//                    dump(i, j, tree.find(j).value);
//                }
                    int l = tree.findLeft(val1);
//                for (int j = 0; j < n - i - 1; j++) {
//                    dump(i, j, tree.find(j).value);
//                }
//                dump("findRight", val2);
                    int r = tree.findRight(val2);
//                for (int j = 0; j < n - i - 1; j++) {
//                    dump(i, j, tree.find(j).value);
//                }
                    // revolve [l,l+1,l+2,...,r] -> [r-t+1,r-t+2,..,r,l,l+1,...,r-t]
                    tree.revolve(l, r, r - node.value);
//                dump("revolve", l, r, r - (node.value));
                }
            }
//        dump(cnt);
            out.println(cnt == 0 ? "YES" : cnt == 1 ? "NO" : "ABSOLUTELY NO");
        }

    }

    static class SplayTreeIndex {
        SplayTreeIndex.Node root;
        final SplayTreeIndex.Node[] sep = new SplayTreeIndex.Node[3];

        int findLeft(int val) {
            SplayTreeIndex.Node cur = root;
            while (true) {
                cur.pushDown();
//            dump("1", cur.value);
                if (cur.left == null) {
                    if (cur.value == val) break;
                    cur = cur.right;
                    continue;
                }

                int minL = cur.left.pushDown().min;
                int maxL = cur.left.pushDown().max;
                if (minL <= val && val <= maxL) {
                    cur = cur.left;
//                dump("3");
                } else {
                    if (cur.value == val) break;
                    cur = cur.right;
//                dump("4");
                }
            }
            root = cur.splay();
            return getCount(cur.left);
        }

        int findRight(int val) {
            SplayTreeIndex.Node cur = root;
            while (true) {
                cur.pushDown();
                if (cur.right == null) {
                    if (cur.value == val) break;
                    cur = cur.left;
                    continue;
                }

                int min = cur.right.pushDown().min;
                int max = cur.right.pushDown().max;
                if (min <= val && val <= max) {
                    cur = cur.right;
                } else {
                    if (cur.value == val) break;
                    cur = cur.left;
                }
            }
            root = cur.splay();
            return getCount(cur.left);
        }

        static int getCount(SplayTreeIndex.Node n) {
            return n == null ? 0 : n.count;
        }

        static SplayTreeIndex.Node getLeft(SplayTreeIndex.Node n) {
            return n == null ? null : n.getLeft();
        }

        static SplayTreeIndex.Node getRight(SplayTreeIndex.Node n) {
            return n == null ? null : n.getRight();
        }

        void insert(int index, int value) {
            insert(index, new SplayTreeIndex.Node(value, null));
        }

        void insert(int index, SplayTreeIndex.Node insertNode) {
            if (root == null) {
                root = insertNode;
                return;
            }
            final int n = getCount(root);
            if (n < index) throw new RuntimeException();
            final SplayTreeIndex.Node add = insertNode;
            if (n == index) {
                SplayTreeIndex.Node node = find(n - 1);
                SplayTreeIndex.Node.linkRight(add, node);
            } else {
                final SplayTreeIndex.Node node = find(index);
                final SplayTreeIndex.Node nl = SplayTreeIndex.Node.cut(node.getLeft());
                SplayTreeIndex.Node.linkLeft(nl, add);
                SplayTreeIndex.Node.linkRight(node, add);
            }
            root = add.splay();
        }

        SplayTreeIndex.Node find(SplayTreeIndex.Node node, int index) {
            while (node != null) {
                node.pushDown();
                if (getCount(node.getLeft()) > index) {
                    node = node.getLeft();
                } else if (getCount(node.getLeft()) == index) {
                    return root = node.splay();
                } else {
                    index -= getCount(node.getLeft()) + 1;
                    node = node.getRight();
                }
            }
            return null;
        }

        SplayTreeIndex.Node find(int index) {
            return find(root, index);
        }

        void remove(final int index) {
            if (index < 0 || getCount(root) <= index) {
                throw new RuntimeException();
            }

            final SplayTreeIndex.Node node = find(index);
            final SplayTreeIndex.Node nl = SplayTreeIndex.Node.cut(node.getLeft());
            final SplayTreeIndex.Node nr = SplayTreeIndex.Node.cut(node.getRight());

            root = SplayTreeIndex.Node.merge(nl, nr);
        }

        SplayTreeIndex.Node[] separate(int l, int r) {
            final SplayTreeIndex.Node left = SplayTreeIndex.Node.cut(getLeft(find(l)));
            final SplayTreeIndex.Node mid = find(r - l);
            final SplayTreeIndex.Node right = SplayTreeIndex.Node.cut(getRight(mid));

            sep[0] = left;
            sep[1] = mid;
            sep[2] = right;

            return sep;
        }

        void revolve(int l, int r, int t) {
            rotate(l, r, t % (r - l + 1));
        }

        void rotate(int l, int r, int t) {
            if (r - l < t) while (true) ;
            SplayTreeIndex.Node[] sep = separate(l, r);

            SplayTreeIndex.Node n = find(sep[1], r - l - t);
            SplayTreeIndex.Node nr = SplayTreeIndex.Node.cut(getRight(n));
            root = SplayTreeIndex.Node.merge(SplayTreeIndex.Node.merge(sep[0], nr), SplayTreeIndex.Node.merge(n, sep[2]));
        }

        void add(int l, int r, int val) {
            SplayTreeIndex.Node[] sep = separate(l, r);
            sep[1].addSubTree(val);
            root = SplayTreeIndex.Node.merge(SplayTreeIndex.Node.merge(sep[0], sep[1]), sep[2]);
        }

        static class Node {
            int value;
            int sum;
            int min;
            int max;
            int count;
            int dval;
            boolean reverse;
            boolean needPushDown;
            SplayTreeIndex.Node left;
            SplayTreeIndex.Node right;
            SplayTreeIndex.Node parent;

            void update() {
                count = 1;
                min = max = sum = value;
                if (getLeft() != null) {
                    count += left.count;
                    sum += left.sum;
                    min = Math.min(min, left.min);
                    max = Math.max(max, left.max);
                }
                if (getRight() != null) {
                    count += right.count;
                    sum += right.sum;
                    min = Math.min(min, right.min);
                    max = Math.max(max, right.max);
                }
                sum += count * dval;
                min += dval;
                max += dval;
            }

            void addSubTree(int val) {
                dval += val;
                sum += val * count;
                needPushDown = true;
            }

            static void receiveLazyValue(SplayTreeIndex.Node n) {
                if (n != null) {
                    n.dval += n.parent.dval;
                    n.reverse ^= n.parent.reverse;
                    n.min += n.parent.dval;
                    n.max += n.parent.dval;
                    n.sum += n.parent.dval * n.count;
                    n.needPushDown = true;
                }
            }

            SplayTreeIndex.Node pushDown() {
                if (needPushDown) {
                    receiveLazyValue(left);
                    receiveLazyValue(right);
                    value += dval;
                    dval = 0;
                    if (reverse) {
                        final SplayTreeIndex.Node n = left;
                        left = right;
                        right = n;
                        reverse = false;
                    }
                    needPushDown = false;
                }
                return this;
            }

            SplayTreeIndex.Node getLeft() {
                pushDown();
                return left;
            }

            SplayTreeIndex.Node getRight() {
                pushDown();
                return right;
            }

            static SplayTreeIndex.Node merge(final SplayTreeIndex.Node nl, final SplayTreeIndex.Node nr) {
                if (nl == null) return nr;
                if (nr == null) return nl;
                nl.splay();
                nr.splay();
                final SplayTreeIndex.Node leftMaxNode = nl.maxNode();
                SplayTreeIndex.Node.linkRight(nr, leftMaxNode);
                return leftMaxNode;
            }

            static void linkLeft(final SplayTreeIndex.Node n, final SplayTreeIndex.Node p) {
                if (p != null) {
                    p.pushDown();
                    cut(p.getLeft());
                    p.left = n;
                }
                if (n != null) {
                    n.parent = p;
                }
                if (p != null) {
                    p.update();
                }
            }

            static void linkRight(final SplayTreeIndex.Node n, final SplayTreeIndex.Node p) {
                if (p != null) {
                    p.pushDown();
                    cut(p.getRight());
                    p.right = n;
                }
                if (n != null) {
                    n.parent = p;
                }
                if (p != null) {
                    p.update();
                }
            }

            static SplayTreeIndex.Node cut(final SplayTreeIndex.Node n) {
                if (n == null || n.parent == null) {
                    return n;
                }
                n.parent.pushDown();
                if (n.parent.left == n) {
                    n.parent.left = null;
                } else {
                    n.parent.right = null;
                }
                n.parent.update();
                n.parent = null;
                return n;
            }

            public Node(int value, SplayTreeIndex.Node parent) {
                this.value = value;
                this.parent = parent;
                update();
            }

            void rotateRight() {
                final SplayTreeIndex.Node x = this;
                final SplayTreeIndex.Node p = x.parent;
                final SplayTreeIndex.Node g = p.parent;
//			if(g != null) g.pushDown();
                p.pushDown();
                x.pushDown();
                p.left = x.right;
                if (x.right != null) {
                    x.right.parent = p;
                }
                p.parent = x;
                x.right = p;
                x.parent = g;
                p.update();
                x.update();
                if (g != null) {
                    if (g.left == p) g.left = x;
                    else if (g.right == p) g.right = x;
//				g.update();
                }
            }

            void rotateLeft() {
                final SplayTreeIndex.Node x = this;
                final SplayTreeIndex.Node p = x.parent;
                final SplayTreeIndex.Node g = p.parent;
//			if(g != null) g.pushDown();
                p.pushDown();
                x.pushDown();
                p.right = x.left;
                if (x.left != null) {
                    x.left.parent = p;
                }
                p.parent = x;
                x.left = p;
                x.parent = g;
                p.update();
                x.update();
                if (g != null) {
                    if (g.left == p) g.left = x;
                    else if (g.right == p) g.right = x;
//				g.update();
                }
            }

            public SplayTreeIndex.Node splay() {
                final SplayTreeIndex.Node x = this;
                while (x.parent != null) {
                    final SplayTreeIndex.Node p = x.parent;
                    if (p.parent == null) {
                        // zig step
                        if (p.getLeft() == x) {
                            x.rotateRight();
                        } else {
                            x.rotateLeft();
                        }
                    } else {
                        final SplayTreeIndex.Node g = p.parent;
                        // zig-zig step / zig-zag step
                        if (g.getLeft() == p) {
                            if (p.getLeft() == x) {
                                p.rotateRight();
                                x.rotateRight();
                            } else {
                                x.rotateLeft();
                                x.rotateRight();
                            }
                        } else {
                            if (p.getLeft() == x) {
                                x.rotateRight();
                                x.rotateLeft();
                            } else {
                                p.rotateLeft();
                                x.rotateLeft();
                            }
                        }
                    }
                }
                return x;
            }

            SplayTreeIndex.Node maxNode() {
                SplayTreeIndex.Node n = this;
                while (true) {
                    n.pushDown();
                    if (n.right == null) break;
                    n = n.right;
                }
                return n.splay();
            }

        }

    }

    static class MyInput {
        private final BufferedReader in;
        private static int pos;
        private static int readLen;
        private static final char[] buffer = new char[1024 * 8];
        private static char[] str = new char[500 * 8 * 2];
        private static boolean[] isDigit = new boolean[256];
        private static boolean[] isSpace = new boolean[256];
        private static boolean[] isLineSep = new boolean[256];

        static {
            for (int i = 0; i < 10; i++) {
                isDigit['0' + i] = true;
            }
            isDigit['-'] = true;
            isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
            isLineSep['\r'] = isLineSep['\n'] = true;
        }

        public MyInput(InputStream is) {
            in = new BufferedReader(new InputStreamReader(is));
        }

        public int read() {
            if (pos >= readLen) {
                pos = 0;
                try {
                    readLen = in.read(buffer);
                } catch (IOException e) {
                    throw new RuntimeException();
                }
                if (readLen <= 0) {
                    throw new MyInput.EndOfFileRuntimeException();
                }
            }
            return buffer[pos++];
        }

        public int nextInt() {
            int len = 0;
            str[len++] = nextChar();
            len = reads(len, isSpace);
            int i = 0;
            int ret = 0;
            if (str[0] == '-') {
                i = 1;
            }
            for (; i < len; i++) ret = ret * 10 + str[i] - '0';
            if (str[0] == '-') {
                ret = -ret;
            }
            return ret;
        }

        public char nextChar() {
            while (true) {
                final int c = read();
                if (!isSpace[c]) {
                    return (char) c;
                }
            }
        }

        int reads(int len, boolean[] accept) {
            try {
                while (true) {
                    final int c = read();
                    if (accept[c]) {
                        break;
                    }
                    if (str.length == len) {
                        char[] rep = new char[str.length * 3 / 2];
                        System.arraycopy(str, 0, rep, 0, str.length);
                        str = rep;
                    }
                    str[len++] = (char) c;
                }
            } catch (MyInput.EndOfFileRuntimeException e) {
            }
            return len;
        }

        public int[] nextIntArray(final int n) {
            final int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt();
            }
            return res;
        }

        static class EndOfFileRuntimeException extends RuntimeException {
        }

    }
}

Submission Info

Judge Result