Unexpected TLE with Segment tree

Правка en2, от jmichael, 2024-01-27 10:03:57

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

Теги tle, segment tree

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский jmichael 2024-01-27 10:03:57 0 (published)
en1 Английский jmichael 2024-01-27 10:03:17 4106 Initial revision (saved to drafts)