Submission #1174211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174211		bhuwan36	Global Warming (CEOI18_glo)	Java	0 / 100	109 ms	23672 KiB

glo

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

public class glo {
	static int search(List<Long> l,long t){
		int i=0,j=l.size();
		while(i<j){
			int mid=i+(j-i)/2;
			if(l.get(mid)<t){
				i=mid+1;
			}
			else j=mid-1;
		}
		return i;
	}
    public static void main(String[] args) {
            FastReader in=new FastReader();
            PrintWriter out = new PrintWriter(System.out);
            boolean p[]=new boolean[100001];
            Arrays.fill(p, true);
            p[0]=false;
            p[1]=false;
            for(int i=2;i<p.length;i++){
                if(!p[i]) continue;
                for(int j=i+1;j<p.length;j+=i){
                    p[j]=false;
                }
            }
            int testcases=in.nextInt();
            while(testcases-- >0){
				int n=in.nextInt();
				long x=in.nextLong();
				long a[]=new long[n];
				for(int i=0;i<n;i++){
					a[i]=in.nextLong();
				}
				// this[i] = the longest subsequence that ends at and contains temps[i]
				int prefLongest[] = new int[n];
				List<Long> lis = new ArrayList<>();
				// standard LIS stuff
				for (int i = 0; i < n; i++) {
					long t = a[i];
					int pos = search(lis, t);
					prefLongest[i] = pos + 1;
					if (pos == lis.size()) {
						lis.add(t);
					} else {
						lis.set(pos, t);
					}
				}

				int longest = 0;
				List<Long> lis2 = new ArrayList<>();
				for (int i = n - 1; i >= 0; i--) {
					long t = a[i];
					// we use negatives here to keep the binary search happy
					// first find the maximum increasing subsequence in the suffix that
					// starts at i
					int pos = search(lis2, -t);
					longest = Math.max(longest, prefLongest[i] + pos);

					// then insert the changed temperature for later iterations
					int insertPos = search(lis2, -t - x);
					if (insertPos == lis2.size()) {
						lis2.add(-t - x);
					} else {
						lis2.set(insertPos, -t - x);
					}
				}
				out.println(longest);
            }

            out.close();
    }
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while(st==null || !st.hasMoreTokens()){
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        char nextChar() {
            return next().charAt(0);
        }
        String nextLine(){
            String str="";
            try {
                str=br.readLine().trim();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}

• 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