Submission #657736

#	Time	Username	Problem	Language	Result	Execution time	Memory
657736		ArkadIA	Global Warming (CEOI18_glo)	Java	100 / 100	379 ms	26104 KiB

glo

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

public class glo {
    static int n, x;
    static int[]t;
    static int[] dt;
    static int[] lenLIS;
    public static int LIS1() {
        ArrayList<Integer> dp = new ArrayList<Integer>();
        for(int i = 0 ; i < dt.length ; ++i){
            int pos = binarySearch(dp, dt[i]);
            lenLIS[i] = pos + 1;
            if (pos >= dp.size()) {
                dp.add(dt[i]);
            } else {
                dp.set(pos, dt[i]);
            }
        }
        return dp.size();
    }
    public static int LIS2() {
        int res = 0;
        ArrayList<Integer> dp = new ArrayList<Integer>();
        for(int i = 0 ; i < t.length ; ++i){
            int pos = binarySearch(dp, t[i]);
            res = Math.max(res, lenLIS[i] + pos);
            pos = binarySearch(dp, t[i] - x);
            if (pos >= dp.size()) {
                dp.add(t[i] - x);
            } else {
                dp.set(pos, t[i] - x);
            }
        }
        return res;
    }
    static int binarySearch(ArrayList<Integer> dp, int x){
        int l = 0, r = dp.size() - 1, mid;
        while(l <= r){
            mid = (l + r + 1)/2;
            if(dp.get(mid) < x)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return l;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(in.readLine());
        n = Integer.valueOf(st.nextToken());
        x = Integer.valueOf(st.nextToken());
        t = new int[n];
        dt = new int[n];
        lenLIS = new int[n];
        st = new StringTokenizer(in.readLine());
        for(int i = 0 ; i < n ; ++i){
            t[i] = Integer.valueOf(st.nextToken());
            dt[n - i - 1] = t[i]*-1;
        }
        LIS1();
        int i = 0, j = n - 1;
        while(i < j){
            int aux = lenLIS[i];
            lenLIS[i] = lenLIS[j];
            lenLIS[j] = aux;
            i++;
            j--;
        }
        System.out.println(LIS2());
        in.close();
        out.flush();
        out.close();
    }
}

• 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