### dutinmeow's blog

By dutinmeow, history, 7 weeks ago,

I am having trouble debugging my persistant li chao tree code for this problem (I know it's not a PLI problem but I need a place to test my code). My code is correct for most small manually generated tests.

Code

Edit: I realized it was something wrong with the driver code (x-coordinates could be negative). If anybody is still interested, my working code can be found here

• +15

 » 7 weeks ago, # |   -19 I think you are picking the wrong platform to ask this on.
 » 6 weeks ago, # |   0 Auto comment: topic has been updated by dutinmeow (previous revision, new revision, compare).
 » 6 weeks ago, # |   0 "persistant"
 » 5 weeks ago, # | ← Rev. 2 →   +1 I tested your code and it seems working only when we update the version 0 of the LiChao Tree. In other words, your code isn't working properly when trying to copy a version to a new one.This is how I tested your code: Testing Code// ... // Here goes your implementation of Persistent LiChao Tree PersistantLiChao ds(-1e9, 1e9); int main() { ios_base::sync_with_stdio(0); cin.tie(0); mt19937 rand32(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution rng(-10, 10); vector::Line> a; for(int i = 0; i < 1000; i++){ ll m = rng(rand32); ll b = rng(rand32); a.push_back({m, b}); ds.add(m, b); } for(int i = 0; i < 1000; i++){ ll x = uniform_int_distribution(-10000000, 10000000)(rand32); ll li_chao = ds.query(x); ll brute_force = LLONG_MIN; for(auto [m, b]:a) brute_force = max(brute_force, m * x + b); assert(li_chao == brute_force); } return 0; } It works fine that way, but as soon as I call to ds.copy() it crashes.UPD: Unluckily (or maybe luckily), the problem where you submitted that code doesn't require to use the PersistantLiChao::copy method, hence you got AC with a wrong template.