Submission #1153680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153680		uranium235	Global Warming (CEOI18_glo)	Java	100 / 100	352 ms	55832 KiB

glo

//package ojuz;

import java.io.*;
import java.util.*;
import java.util.function.IntPredicate;

public class glo {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String[] first = reader.readLine().split(" ");
        int n = Integer.parseInt(first[0]), x = Integer.parseInt(first[1]);
        int[] arr = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // longest lis ending at i
        int[] endsAt = new int[n];
        List<Integer> lis = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int finalI = i;
            int pos = firstTrue(0, lis.size() - 1, j -> arr[finalI] <= lis.get(j));
            endsAt[i] = pos + 1;
            if (pos == lis.size()) lis.add(arr[i]);
            else lis.set(pos, arr[i]);
        }

        lis.clear();
        int best = 0;
        for (int i = n - 1; i >= 0; i--) {
            // since we need to find lis on a normal list, which is equal to finding lds on a reverse list
            // which is equal to finding lis on the reversed list with the elements negated
            int finalI = i;

            // lis starting from the current (un-incremented) element
            int pos = firstTrue(0, lis.size() - 1, j -> -arr[finalI] <= lis.get(j));
            best = Math.max(best, pos + endsAt[i]);

            // now build lis using incremented element
            pos = firstTrue(0, lis.size() - 1, j -> (-arr[finalI] - x) <= lis.get(j));
            if (pos == lis.size()) lis.add(-arr[i] - x);
            else lis.set(pos, -arr[i] - x);

        }

        System.out.println(best);
    }

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

• 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