Блог пользователя jmichael

Автор jmichael, история, 10 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Look at n restrictions again :)

»
10 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

const int MAXN = ...