/*
5 400
300
700
200
1000
500
3 300
700
1000
1300
*/
import java.util.*;
import java.io.*;
public class triusis{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer details = new StringTokenizer(br.readLine());
int n = Integer.parseInt(details.nextToken()); //# of towers
int m = Integer.parseInt(details.nextToken()); //amount that Carrot can jump
long[] towers = new long[n];
TreeMap<Long, Integer> ind = new TreeMap<Long, Integer>(); //for compression of tower heights, as they can be too large to store in the segment tree
int add = 0;
for(int a = 0; a < n; a++){
towers[a] = Long.parseLong(br.readLine()) - (a+1)*m; //normalizes array, don't have to account for Carrot's jumps anymore, just find N - (longest non increasing subsequence)
if(a == 0 && towers[a] > 0){
towers[a] = 0;
add++;
}
ind.put(towers[a], 0);
}
int ct = 0;
for(long item : ind.keySet()) ind.put(item, ct++);
//System.out.println(ind);
//System.out.println(Arrays.toString(towers));
int[] dp = new int[n]; //dp[i] = longest decreasing subsequence ending at i (i is the smallest #)
segTree max = new segTree(n, dp);
for(int a = n - 1; a >= 0; a--){
dp[a] = max.q(ind.get(towers[a]), n-1) + 1;
max.u(ind.get(towers[a]), dp[a]);
}
//System.out.println(Arrays.toString(dp));
System.out.println(n - dp[0] + add);
br.close();
}
}
class segTree{
public int N;
public int[] st; //st = new int[4N/N << 2]
public int[] vals; //initial values
public segTree(int n, int[] vs){
N = n;
vals = vs.clone();
st = new int[n * 4];
build(1, 0, N - 1);
}
public int left(int p){
return 2 * p;
}
public int right(int p){
return 2 * p + 1;
}
public int join(int a, int b){
//take children, update value
//can change this function to change from maximum to sum/minimum
return Math.max(a, b);
}
public void build(int p, int l, int r){
if(l == r) st[p] = vals[l];
else{
build(left(p), l, (l + r)/2);
build(right(p), (l + r)/2 + 1, r);
st[p] = join(st[left(p)], st[right(p)]);
}
}
public void update(int p, int l, int r, int index, int value){
if(index < l || index > r) return;
if(l == r) st[p] = Math.max(st[p], value); //in the case of this problem. in case there are duplicate values
else{
update(left(p), l, (l + r)/2, index, value);
update(right(p), (l + r)/2 + 1, r, index, value);
st[p] = join(st[left(p)], st[right(p)]);
}
}
public int query(int p, int l, int r, int x, int y){
if(x > r || y < l) return 0; //change this to large number/return -1 to calculate minimum, if child == -1 dont include
if(x <= l && y >= r) return st[p];
return join(query(left(p), l, (l + r)/2, x, y), query(right(p), (l + r)/2 + 1, r, x, y));
}
public int q(int left, int right){
return query(1, 0, N - 1, left, right);
}
public void u(int index, int value){
update(1, 0, N - 1, index, value);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8440 KB |
Output is correct |
| 2 |
Correct |
61 ms |
8364 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8440 KB |
Output is correct |
| 2 |
Correct |
61 ms |
8364 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8440 KB |
Output is correct |
| 2 |
Correct |
61 ms |
8364 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
8440 KB |
Output is correct |
| 2 |
Correct |
61 ms |
8364 KB |
Output is correct |
| 3 |
Incorrect |
61 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
