oj.uz

Submission #556331

# Submission time Handle Problem Language Result Execution time Memory
556331 2022-05-03T01:18:28 Z PikaChu999 Rabbit Carrot (LMIO19_triusis) Java 11
0 / 100
 61 ms 8996 KB 
/*
5 400
300
700
200
1000
500
*/
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
    for(int a = 0; a < n; a++){
      towers[a] = Long.parseLong(br.readLine()) - a*m; //normalizes array, don't have to account for Carrot's jumps anymore, just find N - (longest non increasing subsequence)
      ind.put(towers[a], 0);
    }
    
    int ct = 0; 
    for(long item : ind.keySet()) ind.put(item, ct++);
    
    int lds = 0; 
    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 = 0; a < n; a++){
      dp[a] = max.q(ind.get(towers[a]), n-1) + 1; 
      max.u(ind.get(towers[a]), dp[a]);
      lds = Math.max(lds, dp[a]);
    }
    System.out.println(n - lds);
    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);
  }
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8996 KB Output is correct
2 Incorrect 61 ms 8548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8996 KB Output is correct
2 Incorrect 61 ms 8548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8996 KB Output is correct
2 Incorrect 61 ms 8548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8996 KB Output is correct
2 Incorrect 61 ms 8548 KB Output isn't correct
3 Halted 0 ms 0 KB -