...Is here. It is always nice to hear other's approaches as well.
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
...Is here. It is always nice to hear other's approaches as well.
Name |
---|
There is a another solution using Interval Tree.
let's T[v] == 1 if number v is inside the black box, otherwise T[v] == 0
Using array T we can construct interval tree.
Each node will contain basis vectors of existing numbers in it's range.
Initially Array T is filled with 0.
Adding number v, means T[v] = 1
Deleting number v, means T[v] = 0
After each operation we need to update only log(n) nodes.
Can you try to explain a little bit more in detail? I read the article above but I'm having some troubles understanding your solution (and quite honestly the article's) since I'm not familiar with that greedy that solves the static problem. But well, could you provide some more detailed explanation of yours?
I've sent stupid solution and got almost all points (131.71)
Idea is: have a set with current basis and set of others.
Light operations:
Add, delete from others
Heavy operation:
delete from basis.(We should check if there are any element in others that we can add to basis — deleted element. It's O(others_size) but to make it a bit random (More random elements go to current basis, so it's harder to remove them and not element from others) I support an iterator to the set of others and check all element of others in order [iter, end), then [begin, iter), not [begin, end) but I am not sure if it helped at all (probably just check from begin to end will work too)
That a thing why I don't really like contests with not full solutions getting points.
I have similar solution (n*30*30) and got AC. Idea is to keep basis with most long-living elements.
Am I right that your solution is basically offline and you precalculated for each element when it'll be deleted?
PS: I don't see you in top of scoreboard. Did you sent it after the end of contest?
Yes, my solution is offline. Yes, during the contest I had bug =)