Hello, about 4 months ago i tried to solve 678F - Лена и запросы using LI Chao tree and trick to delete lines from it(trick), but got WA9. After that i stopped trying to solve it. But today i started from the very beginning and still it is WA9. Here is my last submission: 100175660. Can you help me?
UPD: I finally found where was an error. I used pointer incorrectly, here is solution that works: 100181898. If someone else is facing same problem try to write your update like this:
node* upd(pll val, node *v = r, ll tl = -inf, ll tr = inf) {
if (v == nullptr)
v = new node();
ll tm = tl + tr >> 1;
if (v->val.F * tm + v->val.S <= val.F * tm + val.S) {
s.push({v, v->val});
swap(val, v->val);
}
if (tl + 1 == tr)
return v;
if (v->val.F * tl + v->val.S >= val.F * tl + val.S)
v->r = upd(val, v->r, tm, tr);
else
v->l = upd(val, v->l, tl, tm);
return v;
}
In solution with an error i made upd as a void function, i think that i need to improve my understanding of pointers in C++.