Submission #1153678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153678		uranium235	Global Warming (CEOI18_glo)	Java	0 / 100	267 ms	47440 KiB

glo

//package ojuz;

import java.io.*;
import java.util.*;

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 pos = Collections.binarySearch(lis, arr[i]);
            if (pos < 0) pos = -pos - 1;
            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
            arr[i] = -arr[i];
            
            // lis starting from the current (un-incremented) element
            int pos = Collections.binarySearch(lis, arr[i]);
            if (pos < 0) pos = -pos - 1;
            best = Math.max(best, pos + endsAt[i]);

            // now build lis using incremented element
            pos = Collections.binarySearch(lis, arr[i] + x);
            if (pos < 0) pos = -pos - 1;
            if (pos == lis.size()) lis.add(arr[i]);
            else lis.set(pos, arr[i]);
        }

        System.out.println(best - 1);
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25