Submission #1128397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128397		Oz121	Global Warming (CEOI18_glo)	Java	100 / 100	358 ms	50564 KiB

glo

import java.io.*;
import java.util.*;
public class glo {
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine()); int num = Integer.parseInt(l1.nextToken()); int x = Integer.parseInt(l1.nextToken());
        int[] arr = new int[num]; StringTokenizer st = new StringTokenizer(scan.readLine());
        for (int i = 0;i<num;i++) arr[i] = Integer.parseInt(st.nextToken());

        int[] pLIS = new int[num]; //For each i, store the LIS up to i that includes arr[i]
        ArrayList<Integer> dp = new ArrayList<>();
        for (int i = 0;i<num;i++) {
            int pos = Collections.binarySearch(dp, arr[i]);
            if (pos<0) pos = (-1)*pos-1;

            if (pos==dp.size()) dp.add(arr[i]);
            else dp.set(pos, arr[i]);

            pLIS[i] = pos+1;
        }

        int[] sLIS = new int[num]; //For each i, store the LIS from i->num-1 that has minimum number > arr[i]-x
        dp = new ArrayList<>();
        for (int i = num-1;i>=0;i--) {
            int idx = Collections.binarySearch(dp, arr[i]-x+1, (k,j)->j-k);
            if (idx<0) idx = (-1)*idx-2;
            sLIS[i] = idx+1;

            int pos = Collections.binarySearch(dp, arr[i], (k,j)->j-k);
            if (pos<0) pos = (-1)*pos-1;

            if (pos==dp.size()) dp.add(arr[i]);
            else dp.set(pos, arr[i]);
        }

        int ans = Math.max(pLIS[num-1], sLIS[0]);
        for (int i = 0;i<num-1;i++) {
            ans = Math.max(ans, pLIS[i]+sLIS[i]);
        }
        System.out.println(ans);
    }
}

• 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