Submission #1153678

#TimeUsernameProblemLanguageResultExecution timeMemory
1153678uranium235Global Warming (CEOI18_glo)Java
0 / 100
267 ms47440 KiB
//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);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...