Please read the new rule regarding the restriction on the use of AI tools. ×

Unexpected TLE with Segment tree

Revision en1, by jmichael, 2024-01-27 10:03:17

Unexpected TLE with Segment tree

My solution to 1919F1 - Wine Factory (Easy Version) involved a few observations

  1. Since the capacity of pipes are infinite in the easy version, each tank will transfer all remaining water to the next tank, and we can imagine the last tank dumping water outside
  2. Now suppose we can also add water in from the left. How will the water that is dumped out from the right change?
  3. I realized that there is a base amount that will always be dumped. As I starting adding water from the left, there will be initially no change, but after a certain cutoff, the the amount of water dumped will increase.
  4. So a system of water tanks can be characterized by two values — base and cutoff
  5. Also two systems of water tanks can be composed. We can derive the base and cutoff of the larger system.
  6. Using a segment tree, we can exploit this to make updates fast
  7. The total amount of water and wine is conserved.

The logic seems right enough, since it ran till test 10, but encountered a TLE there. However the time complexity is O(n logn) for building the segment tree and O(q logn) for answering the queries. The constant factors also don't seem very large. I made some optimizations (replaced pair <int, int> with array) and tried again without success. What is the cause of this?

My solution

Links to my attempts

Tags tle, segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English jmichael 2024-01-27 10:03:57 0 (published)
en1 English jmichael 2024-01-27 10:03:17 4106 Initial revision (saved to drafts)