Abhi complexity q*log n*log n hai ....ham ese kar sakte h ki new tree bnale har baar?

#1

ham har query k liy new segment tree nhi bana sakte ?? or tree mei number of elements >=k rakhvale??? bs complexity abhi jitni hai *log n ho jaygi…i guess zada fark nhi padega???

#2

tle aara hai :frowning: , that means hamesha segment tree 1 hi bnega pure question mei ?? uspar saari queries hogi??

#3

@Muskan-Gupta-598128740703036,
Complexity of creating a tree = Complexity of creating a node * Number of Nodes (Simple unitary method).
So you can see complexity of creating a tree(here) would be O(nlog(n)) where n is number of leaves. And, we obviously need to answer any query in almost O(log(n)). So, yeah TLE is inevitable if we create a new tree for each query. In fact simply iterating from l to r would be better than doing that.

#4
#5

kch azeeb si error aari hai isme

#6

ye —> Main.java uses unchecked or unsafe operations.

#7

?? i am waiting for reply

#8

@Muskan-Gupta-598128740703036,
Sorry for the inconvenience, but I don’t have any experience in Java, please wait for a while, I will ask someone to resolve the doubt.

#9

Han g , its ohk fine :slight_smile:

#10

sir i am waiting???

#11

@sanjeetboora,
Sir, Please assign this doubt to some Java guy.

#12

hi @Muskan-Gupta-598128740703036
i m here to help you out can you send me the problem link as i have to read the problem statement first.

#13

https://online.codingblocks.com/app/player/66903/content/66010/4858/code-challenge

#14
#15

@Muskan-Gupta-598128740703036
I can’t open it can you send me the problem statement along with sample test case.

#16

Hey @Muskan-Gupta-598128740703036,

https://ide.codingblocks.com/s/204277 I have corrected your code here. I have used a lot of collections methods and made a lot changes so feel free to ask me about anything regarding the code.

But the issue with this is that it will not pass TLE in the question. See, this is a question of Competitive Programming course and Segment trees. I highly doubt that it’s meant to be done in Java since it’s a slower language than CPP.

The key difference is execution time. CPP has a far less execution time as compared to Java and if you use ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); in CPP, it further reduces your execution time. Also, Scanner class takes a lot of time to process the inputs. Instead try to use the FastReader class for Input/Output instead of the regular Scanner class.

Now it doesn’t mean that Java is not a good language to learn or code in.

If you take a Java program and translate it to C++, the result will almost certainly run slower.

If you take a C++ program and translate it to Java, that too will also run slower.

Not because one language is “faster” than the other, but because the original program was written for one language, and was tailored to work well in that language. Now in your case, this question was tailor made for CPP, so doing it in Java will give you a TLE with a very high probability.

Also, regarding the code that I posted, feel free to tag me on this thread if you have any further doubts. :smile:

#17

sir mujhe fast input output lene nhi aate abhi java mei , toh aap ek baar code mei reader use krke dekhlo kya pta cases paas ho jay ?

#18

@Muskan-Gupta-598128740703036,
https://ide.codingblocks.com/s/204289 Here is the code with FastReader class. Again as I said, it will give TLE.

Try and understand this :smile: :
If you take a Java program and translate it to C++, the result will almost certainly run slower.

If you take a C++ program and translate it to Java, that too will also run slower.

Not because one language is “faster” than the other, but because the original program was written for one language, and was tailored to work well in that language.

#19

ya but meine sir ko bol diya h time limit increase krne k liy

#20

Hey @Muskan-Gupta-598128740703036,

https://ide.codingblocks.com/s/205080 Here is the code which you can submit and it will give you a correct answer :smile:

What I have done:

  1. First there is the FastReader class. Which we will use instead of scanner. Next is the main method. In that we make our tree arraylist of the type Arraylist which means that we will use an arraylist to store arraylists of the type Long.

  2. Now after taking inputs, we need to put 4*n+1 empty arraylists inside our tree arraylist not doing so will give an out of bounds exception. It will give an error because there will be no arraylist on any index when we start building our tree. Hence the error.

  3. After that I have used .addAll method to append the arraylist and then Collections.sort to sort the arraylist in build method.

  4. In the query method, Collections.binarySearch is being used to find the lowerbound of k in the arraylist.

If you any query regarding the code, feel free to reply to me on this thread. :smiley:

Also, you can check the time taken by Scanner class and Fastreader by submitting individually in both classes.

FastReader takes Less than or just about 4 seconds, whereas Scanner takes Around 5.5 seconds.