Strip: Round 278 D1 Problem 2

Правка en2, от quinamatics, 2017-08-28 00:07:55

why the fuck am I getting runtime error on test cases 26 and 29? code is below

import java.util.LinkedList; import java.util.Scanner;

public class Strip { public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    String str = sc.nextLine(); String[] strarr = str.split(" ");

    int n = Integer.parseInt(strarr[0]);
    int s = Integer.parseInt(strarr[1]);
    int l = Integer.parseInt(strarr[2]);


    LinkedList<Pair> dmax = new LinkedList<Pair>();
    LinkedList<Pair> dmin = new LinkedList<Pair>();
    int[] arr = new int[n];
    int[] f = new int[n]; //least # of cuts needed
    int[] g = new int[n];//leftmost index of right strip
    int tail = 0;

    g[0] = 0;  
    for(int i = 0; i < l; ++i){
       f[i] = 69696969;
    }
    str = sc.nextLine();strarr = str.split(" ");
    for(int i = 0; i < strarr.length; i++){
       arr[i] = Integer.parseInt(strarr[i]);
    }




    dmin.add(new Pair(arr[0],0));
    dmax.add(new Pair(arr[0],0));
    //Monotonic Queue
    for(int i = 1; i < n; i++){
       while(!dmax.isEmpty()&&(arr[i]>=dmax.getLast().val))
         dmax.pollLast();
       dmax.add(new Pair(arr[i],i));

       while(!dmin.isEmpty()&&(arr[i]<=dmin.getLast().val))
         dmin.pollLast();
       dmin.add(new Pair(arr[i],i));

       while(!dmax.isEmpty() && !dmin.isEmpty()&&(dmax.getFirst().val -dmin.getFirst().val > s)){
         ++tail;
         if(dmax.getFirst().pos < tail)
          dmax.poll();
         if(dmin.getFirst().pos<tail)
          dmin.poll();
       }
       g[i] = tail;
    }



    dmin = new LinkedList<Pair>();
    dmin.add(new Pair(0,-1));
    if(g[l-1]==0)
       f[l-1]=1;
    else{
       System.out.println(-1);
       return;
    }

    for(int i = l; i < n; i++){
       f[i]= 69696969;
       while(!dmin.isEmpty() && f[i-l] <= dmin.getLast().val)
         dmin.pollLast();

       dmin.add(new Pair(f[i-l],i-l));

       while(!dmin.isEmpty() && dmin.getFirst().pos < g[i]-1)
         dmin.poll();
       if(!dmin.isEmpty())
         f[i] = dmin.getFirst().val+1;
    }
    if(f[n-1] < 69696969)  
       System.out.println(f[n-1]);
    else
       System.out.println(-1);
}

static class Pair
{
    int val;
    int pos;
    public Pair(int val, int pos)
    {
        this.val = val;
        this.pos = pos;
    }

}

}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский quinamatics 2017-08-30 02:26:29 8 Tiny change: 'y the fuck am I' -> 'y the fucking fuck am I'
en3 Английский quinamatics 2017-08-28 00:08:13 0 (published)
en2 Английский quinamatics 2017-08-28 00:07:55 136 (saved to drafts)
en1 Английский quinamatics 2017-08-28 00:07:02 2471 Initial revision (published)