Submission #590103

#	Time	Username	Problem	Language	Result	Execution time	Memory
590103		DylanSmith	Global Warming (CEOI18_glo)	Java	100 / 100	610 ms	25792 KiB

glo

import java.util.*;
import java.io.*;
public class glo {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt(), K = in.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }
        List<Integer> compress = new ArrayList<>();
        for (int i : arr) {
            compress.add(i);
        }
        Collections.sort(compress);
        for (int i = 0; i < N; i++) {
            arr[i] = Collections.binarySearch(compress, arr[i]);
        }
        int[] up = new int[compress.size()];
        int index = 0;
        for (int i = 0; i < compress.size(); i++) {
            while (index + 1 < compress.size() && compress.get(index + 1) < compress.get(i) + K) {
                index++;
            }
            up[i] = index;
        }
        int M = 1;
        while (M < compress.size()) {
            M <<= 1;
        }
        int[] tree = new int[M * 2], tree2 = new int[M * 2];
        for (int i : arr) {
            int l = M, r = i - 1 + M;
            int max = 0, max2 = 0;
            while (l <= r) {
                if (l % 2 == 1) {
                    max = Math.max(max, tree[l]);
                    max2 = Math.max(max2, tree2[l]);
                    l >>= 1;
                    l++;
                } else {
                    l >>= 1;
                }
                if (r % 2 == 0) {
                    max = Math.max(max, tree[r]);
                    max2 = Math.max(max2, tree2[r]);
                    r >>= 1;
                    r--;
                } else {
                    r >>= 1;
                }
            }
            l = M;
            r = up[i] + M;
            while (l <= r) {
                if (l % 2 == 1) {
                    max2 = Math.max(max2, tree[l]);
                    l >>= 1;
                    l++;
                } else {
                    l >>= 1;
                }
                if (r % 2 == 0) {
                    max2 = Math.max(max2, tree[r]);
                    r >>= 1;
                    r--;
                } else {
                    r >>= 1;
                }
            }
            max++;
            max2++;
            int current = i + M;
            while (current > 0) {
                tree[current] = Math.max(tree[current], max);
                tree2[current] = Math.max(tree2[current], max2);
                current >>= 1;
            }
        }
        out.println(tree2[1]);
        
        out.close();
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

• 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