oj.uz

Submission #526561

# Submission time Handle Problem Language Result Execution time Memory
526561 2022-02-15T08:38:50 Z Longgggggggg Global Warming (CEOI18_glo) Java 11
100 / 100
 379 ms 26264 KB 
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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9252 KB Output is correct
2 Correct 73 ms 9036 KB Output is correct
3 Correct 78 ms 9208 KB Output is correct
4 Correct 85 ms 8988 KB Output is correct
5 Correct 76 ms 8912 KB Output is correct
6 Correct 80 ms 9116 KB Output is correct
7 Correct 79 ms 9196 KB Output is correct
8 Correct 71 ms 8988 KB Output is correct
9 Correct 75 ms 9092 KB Output is correct
10 Correct 74 ms 9012 KB Output is correct
11 Correct 74 ms 8920 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9252 KB Output is correct
2 Correct 73 ms 9036 KB Output is correct
3 Correct 78 ms 9208 KB Output is correct
4 Correct 85 ms 8988 KB Output is correct
5 Correct 76 ms 8912 KB Output is correct
6 Correct 80 ms 9116 KB Output is correct
7 Correct 79 ms 9196 KB Output is correct
8 Correct 71 ms 8988 KB Output is correct
9 Correct 75 ms 9092 KB Output is correct
10 Correct 74 ms 9012 KB Output is correct
11 Correct 74 ms 8920 KB Output is correct
12 Correct 71 ms 9088 KB Output is correct
13 Correct 74 ms 8948 KB Output is correct
14 Correct 72 ms 8984 KB Output is correct
15 Correct 72 ms 9136 KB Output is correct
16 Correct 85 ms 9004 KB Output is correct
17 Correct 75 ms 9052 KB Output is correct
18 Correct 72 ms 9108 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9252 KB Output is correct
2 Correct 73 ms 9036 KB Output is correct
3 Correct 78 ms 9208 KB Output is correct
4 Correct 85 ms 8988 KB Output is correct
5 Correct 76 ms 8912 KB Output is correct
6 Correct 80 ms 9116 KB Output is correct
7 Correct 79 ms 9196 KB Output is correct
8 Correct 71 ms 8988 KB Output is correct
9 Correct 75 ms 9092 KB Output is correct
10 Correct 74 ms 9012 KB Output is correct
11 Correct 74 ms 8920 KB Output is correct
12 Correct 71 ms 9088 KB Output is correct
13 Correct 74 ms 8948 KB Output is correct
14 Correct 72 ms 8984 KB Output is correct
15 Correct 72 ms 9136 KB Output is correct
16 Correct 85 ms 9004 KB Output is correct
17 Correct 75 ms 9052 KB Output is correct
18 Correct 72 ms 9108 KB Output is correct
19 Correct 102 ms 9768 KB Output is correct
20 Correct 108 ms 9640 KB Output is correct
21 Correct 98 ms 9924 KB Output is correct
22 Correct 98 ms 9808 KB Output is correct
23 Correct 101 ms 10460 KB Output is correct
24 Correct 108 ms 10388 KB Output is correct
25 Correct 99 ms 10396 KB Output is correct
26 Correct 100 ms 10156 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 17972 KB Output is correct
2 Correct 333 ms 17840 KB Output is correct
3 Correct 329 ms 18140 KB Output is correct
4 Correct 333 ms 17972 KB Output is correct
5 Correct 313 ms 24752 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 14616 KB Output is correct
2 Correct 254 ms 14524 KB Output is correct
3 Correct 231 ms 14576 KB Output is correct
4 Correct 245 ms 15840 KB Output is correct
5 Correct 73 ms 9108 KB Output is correct
6 Correct 221 ms 15924 KB Output is correct
7 Correct 255 ms 14776 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 15756 KB Output is correct
2 Correct 249 ms 15764 KB Output is correct
3 Correct 302 ms 18048 KB Output is correct
4 Correct 323 ms 24952 KB Output is correct
5 Correct 235 ms 18496 KB Output is correct
6 Correct 308 ms 24632 KB Output is correct
7 Correct 338 ms 25404 KB Output is correct
8 Correct 255 ms 15540 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 9252 KB Output is correct
2 Correct 73 ms 9036 KB Output is correct
3 Correct 78 ms 9208 KB Output is correct
4 Correct 85 ms 8988 KB Output is correct
5 Correct 76 ms 8912 KB Output is correct
6 Correct 80 ms 9116 KB Output is correct
7 Correct 79 ms 9196 KB Output is correct
8 Correct 71 ms 8988 KB Output is correct
9 Correct 75 ms 9092 KB Output is correct
10 Correct 74 ms 9012 KB Output is correct
11 Correct 74 ms 8920 KB Output is correct
12 Correct 71 ms 9088 KB Output is correct
13 Correct 74 ms 8948 KB Output is correct
14 Correct 72 ms 8984 KB Output is correct
15 Correct 72 ms 9136 KB Output is correct
16 Correct 85 ms 9004 KB Output is correct
17 Correct 75 ms 9052 KB Output is correct
18 Correct 72 ms 9108 KB Output is correct
19 Correct 102 ms 9768 KB Output is correct
20 Correct 108 ms 9640 KB Output is correct
21 Correct 98 ms 9924 KB Output is correct
22 Correct 98 ms 9808 KB Output is correct
23 Correct 101 ms 10460 KB Output is correct
24 Correct 108 ms 10388 KB Output is correct
25 Correct 99 ms 10396 KB Output is correct
26 Correct 100 ms 10156 KB Output is correct
27 Correct 332 ms 17972 KB Output is correct
28 Correct 333 ms 17840 KB Output is correct
29 Correct 329 ms 18140 KB Output is correct
30 Correct 333 ms 17972 KB Output is correct
31 Correct 313 ms 24752 KB Output is correct
32 Correct 260 ms 14616 KB Output is correct
33 Correct 254 ms 14524 KB Output is correct
34 Correct 231 ms 14576 KB Output is correct
35 Correct 245 ms 15840 KB Output is correct
36 Correct 73 ms 9108 KB Output is correct
37 Correct 221 ms 15924 KB Output is correct
38 Correct 255 ms 14776 KB Output is correct
39 Correct 248 ms 15756 KB Output is correct
40 Correct 249 ms 15764 KB Output is correct
41 Correct 302 ms 18048 KB Output is correct
42 Correct 323 ms 24952 KB Output is correct
43 Correct 235 ms 18496 KB Output is correct
44 Correct 308 ms 24632 KB Output is correct
45 Correct 338 ms 25404 KB Output is correct
46 Correct 255 ms 15540 KB Output is correct
47 Correct 264 ms 15892 KB Output is correct
48 Correct 270 ms 15628 KB Output is correct
49 Correct 330 ms 17872 KB Output is correct
50 Correct 316 ms 24904 KB Output is correct
51 Correct 379 ms 23984 KB Output is correct
52 Correct 280 ms 25416 KB Output is correct
53 Correct 333 ms 25412 KB Output is correct
54 Correct 330 ms 26264 KB Output is correct
55 Correct 301 ms 18184 KB Output is correct