Submission #583998

#	Time	Username	Problem	Language	Result	Execution time	Memory
583998		DylanSmith	Rabbit Carrot (LMIO19_triusis)	Java	100 / 100	646 ms	55916 KiB

triusis

import java.util.*;
import java.io.*;
public class triusis {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt() + 1, K = in.nextInt();
        long[] arr = new long[N];
        for (int i = 1; i < N; i++) {
            int h = in.nextInt();
            arr[i] = h - i * K;
        }
        TreeSet<Long> set = new TreeSet<>();
        for (long i : arr) {
            set.add(i);
        }
        HashMap<Long, Integer> map = new HashMap<>();
        int index = 0;
        for (long i : set) {
            map.put(i, index++);
        }
        int[] arr2 = new int[N];
        for (int i = 0; i < N; i++) {
            arr2[i] = map.get(arr[i]);
        }
        int M = 1;
        while (M < 200001) {
            M <<= 1;
        }
        int[] tree = new int[M * 2];
        for (int i = 0; i < N; i++) {
            int l = arr2[i] + M, r = M * 2 - 1;
            int max = 0;
            while (l <= r) {
                if (l % 2 == 1) {
                    max = Math.max(max, tree[l]);
                    l >>= 1;
                    l++;
                } else {
                    l >>= 1;
                }
                if (r % 2 == 0) {
                    max = Math.max(max, tree[r]);
                    r >>= 1;
                    r--;
                } else {
                    r >>= 1;
                }
            }
            if (i > 0 && max == 0) {
                continue;
            }
            max++;
            int current = arr2[i] + M;
            while (current > 0) {
                tree[current] = Math.max(tree[current], max);
                current >>= 1;
            }
        }
        out.println(N - tree[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: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37