| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1174209 | bhuwan36 | Global Warming (CEOI18_glo) | Java | 0 ms | 0 KiB |
import java.util.*;
import java.io.*;
public class D_Simple_Permutation {
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;
}
}
}