Submission #526561

#	Time	Username	Problem	Language	Result	Execution time	Memory
526561		Longgggggggg	Global Warming (CEOI18_glo)	Java	100 / 100	379 ms	26264 KiB

glo

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

public class glo {
    public static void main(String[] args) {
        FastIO io = new FastIO();
        int n = io.nextInt();
        int k = io.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) arr[i] = io.nextInt();

        int[] leftLIS = new int[n];
        ArrayList<Long> ll = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            long val = arr[i];
            int upp = firstTrue(0, ll.size() - 1, (x) -> ll.get(x) >= val);
            if (upp == ll.size()) ll.add(val);
            ll.set(upp, val);
            leftLIS[i] = upp + 1;
        }

        ArrayList<Long> rl = new ArrayList<>();
        int ans = ll.size();
        for (int i = n - 1; i > 0; i--) {
            long val = arr[i] + k;
            int low = firstTrue(0, rl.size() - 1, (x) -> rl.get(x) <= val);
            if (low == rl.size()) rl.add(val);
            rl.set(low, val);

            int finalI = i;
            int rLIS = lastTrue(0, rl.size()-1, (x) -> rl.get(x) > arr[finalI - 1]) + 1;
            ans = Math.max(ans, rLIS + leftLIS[i - 1]);
        }
        io.println(ans);
        io.close();
    }

    private static int lastTrue(int lo, int hi, Predicate<Integer> test) {
        lo--;
        for (int dif = hi - lo; dif > 0; dif /= 2) {
            while (lo + dif <= hi && test.test(lo + dif)) {
                lo += dif;
            }
        }
        return lo;
    }

    private 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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25