rgoewedky's blog

By rgoewedky, history, 4 years ago, In English

https://cses.fi/problemset/task/1091

I am getting TLE in two cases.

Here is my code:

import java.io.*;
import java.util.*;
public class Solution {
    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        String next() { // reads in the next string
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() { return Integer.parseInt(next()); } // reads in the next int
        public long nextLong() { return Long.parseLong(next()); } // reads in the next long
        public double nextDouble() { return Double.parseDouble(next()); } // reads in the next double
    }
     
    static InputReader f= new InputReader(System.in);
    static PrintWriter out= new PrintWriter(System.out);
    public static void main(String[] args) {
        // YOUR CODE HERE //! @ % & * () _ {} # ~ : < > ? "" | ^

        int n=f.nextInt();
        int m=f.nextInt();
        int x=0,ind=0;
    
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for (int i=0;i<n;i++) {
            x=f.nextInt();
            if (map.containsKey(x)) {
                map.put(x,map.get(x)+1);
            }
            else map.put(x,1);
        }

        //sort(a);

        for (int i=0;i<m;i++) {
            x=f.nextInt();
            //ind=lower_bound(a,x);

            if (map.containsKey(x)) {
                
                if (map.get(x)>0) {
                    out.println(x);
                   map.put(x,map.get(x)-1);

                   if (map.get(x)==0) {
                       map.remove(x);
                   }
                }

                else {
                    out.println(-1);
                   // map.put(x,map.get(x)-1);
                }
                
            }

            else if (map.lowerKey(x)!=null) {
                if (map.get(map.lowerKey(x))>0) {
                    out.println(map.lowerKey(x));
                   map.put(map.lowerKey(x),map.get(map.lowerKey(x))-1);

                   if (map.get(map.lowerKey(x))==0) {
                       map.remove(map.lowerKey(x));
                   }
                }
                else out.println(-1);
            }
            else out.println(-1);
        }



        out.close(); // flushes the output once printing is done
    }
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bro have you got the answer?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

You can search on the web as in this questions the contraints are very tight and java submissions are getting TLE. My friend had also struggled in the same question from CSES. My websites had given the most optimal code for the problem but majority doesn't work.

I would suggest to just submit the C++ code as you already know the most optimal approach of the problem.