Submission #657735

#TimeUsernameProblemLanguageResultExecution timeMemory
657735ArkadIAGlobal Warming (CEOI18_glo)Java
0 / 100
378 ms21176 KiB
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 < dt.length ; ++i){
            int pos = binarySearch(dp, dt[i]);
            res = Math.max(res, lenLIS[i] + pos);
            pos = binarySearch(dp, dt[i] - x);
            if (pos >= dp.size()) {
                dp.add(dt[i] - x);
            } else {
                dp.set(pos, dt[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();
    }
}
#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...