algorithmdata-structuressegment-tree
Getting Wrong Answer on CSES Problem Set Hotel Queries
https://cses.fi/problemset/task/1143/
I am trying to solve this problem, I used Segment Tree for solving it. I tried every possible test cases but it is not getting accepted.
Just failing in one test case which is too big. Please help me out to solve this problem ..!!!
Solution : https://cses.fi/paste/072a5f07ec4a533b18c669/
Solution
The problem is when a group of guests don't fit. Your code will recurse down the right spine, then go past because the test l == r && seg[index] >= val will be false. The result is that you treat the leaf corresponding to the last hotel as a branch and zero it out as the max of the two empty children whose seg values are uninitialized.
If I'm right, then this test should fail:
1 2
1
2 1
- Is the inorder predecessor of a node with no left subtree and being the left child of its parent always its grandparent?
- How to calculate rounded corners for a polygon?
- Is the Inorder Predecessor of a Node with a Left Subtree Always a Leaf Node in a Binary Search Tree?
- Codility Leader Algorithm in JavaScript
- Tricky Google interview question
- Java problem time limit exceeded issue
- Can we get a better complexity than O(n) for cumulative sum while using multithreading?
- Fastest method to define whether a number is a triangular number
- What is a plain English explanation of "Big O" notation?
- How can I get the length of repeating decimal?
- Splitting dag dependencies in python
- How to find the time comlexity when comparing sublists?
- Clarification on `length = prefixTable[length - 1]` vs. `length = length - 1` in the KMP Algorithm
- Swapping two numbers using only two variables
- Fastest way to fill an array with a single value
- Algorithm for minimizing the amount of lines to draw?
- Convert Excel Column Number to Column Name in Matlab
- Find n-element in sequence. How to speed up the programm (time) for n > 10^6?
- O(n log n) algorithm to find number of large inversions
- Algorithm for drawing lines with 90-degree angles
- Depth First Search v.s. Greedy Best First Search
- How to improve pandas DF processing time on different combinations of calculated data
- How to speed up search in a huge dictionary
- Gradient Of Bezier Curve At Given Point
- How many ways can I choose numbers (repeatable) from a set that amount to the same sum?
- How can building a heap be O(n) time complexity?
- What is the reason why std::rotate() is implemented this way?
- String to string compression algorithm?
- Computing index from timestamp
- Forward chaining and Backward chaining in java