Submission #525672

#	Time	Username	Problem	Language	Result	Execution time	Memory
525672		Longgggggggg	Rabbit Carrot (LMIO19_triusis)	Java	100 / 100	204 ms	19532 KiB

triusis

import java.io.*;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.function.Predicate;

public class triusis {
    public static void main(String[] args) {
        FastIO io = new FastIO();
        int n = io.nextInt();
        int m = io.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) arr[i] = -(io.nextInt() - i * m);
        ArrayList<Integer> l = new ArrayList<>();
        l.add(0);
        for (int i = 1; i <= n; i++) {
            int val = arr[i];
            int upper = firstTrue(0, l.size() - 1, (x) -> l.get(x) > val);
            if (upper == 0) continue;
            if (upper == l.size()) l.add(val);
            l.set(upper, val);
        }
        io.println(n - l.size() + 1);
        io.close();
    }

    public static int firstTrue(int lo, int hi, Predicate<Integer> test) {
        hi++;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (test.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    private static class FastIO extends PrintWriter {
        private final InputStream stream;
        private final byte[] buf = new byte[1 << 16];
        private int curChar, numChars;

        // standard input
        public FastIO() {
            this(System.in, System.out);
        }

        public FastIO(InputStream i, OutputStream o) {
            super(o);
            stream = i;
        }

        // file input
        public FastIO(String i, String o) throws IOException {
            super(new FileWriter(o));
            stream = new FileInputStream(i);
        }

        // throws InputMismatchException() if previously detected end of file
        private int nextByte() {
            if (numChars == -1) throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars == -1) return -1; // end of file
            }
            return buf[curChar++];
        }

        // to read in entire lines, replace c <= ' '
        // with a function that checks whether c is a line break
        public String next() {
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = nextByte();
            } while (c > ' ');
            return res.toString();
        }

        public int nextInt() { // nextLong() would be implemented similarly
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public long nextLong() { // nextLong() would be implemented similarly
            int c;
            do {
                c = nextByte();
            } while (c <= ' ');
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = nextByte();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') throw new InputMismatchException();
                res = 10 * res + c - '0';
                c = nextByte();
            } while (c > ' ');
            return res * sgn;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37