I’m trying for a couple of days to solve this problem (https://www.codechef.com/problems/SPOOL ) with a basic approach (btw I was expecting to obtain a TLE but only WA which makes me think that either I’m doing something very wrong):
- keep an array of depths (guarded the array with 0) to simulate the overflow of the pool
- for every query of type 2 just return the depth from previous array
- for every query of type 1 do the following
- compute the segment [start, end] that has same depth as the query point
- if both depth[start] & depth[end] > depth[queryPoint] fill recursively on start and end with v/2
- elseif depth[start] or depth[end] > depth[queryPoint] and other head of segment is lower then fill that point start or end with v
- elseif both depths are lower than queryPoint - try to fill that point up to the closest depth and then repeat the process with the rest of volume.
Code is here.
I’ve compared my solutions with the ones passing the tests and I couldn’t find tests that have different output (different in comments of more than 1e-6)