### tzc_wk's blog

By tzc_wk, history, 9 months ago,

I've thought of another solution of problem D during the contest, which may also be possible.

Let $S_{i,0}$ be the set of intervals that overlaps with interval in venue A, and $S_{i,1}$ be the set of intervals that overlaps with interval in venue B. Then we only need to check $S_{i,0}!=S_{i,1}$.

As a set is hard to express, we can express them in the binary form, i.e. the $2^0$ digit of the binary form is $1$ if the $i$-th interval overlaps with interval $1$, $0$ otherwise; the $2^1$ digit of the binary form is $1$ if the $i$-th interval overlaps with interval $1$, $2$ otherwise and so on. As the number is rather large, we may modulo with a large number, for example $993244853$. Then the only thing we need to do is calculate $S_{i,0}$ and $S_{i,1}$.

Take venue A as an example. We may find that $S_{i,0}$ equals to the whole set $-$ the set of intervals that do not intersect with them. Suppose there is an interval $[a,b]$, then interval $[c,d]$ do not intersect with it if and only if $d<a$ or $c>b$. To calculate the first situation, we can sort the intervals by left bound non-decreasing order, add $2^{id_i}$ on position $y_i$ using BIT, where $id_i$ is the original index of the interval, and the set of the first situation equals to $sum(x_i-1)$. To calculate the second situation, we can sort the intervals by right bound non-increasing order, add $2^{id_i}$ on position $x_i$ using BIT, where $id_i$ is the original index of the interval, and the set of the first situation equals to $sum(1e9)-sum(y_i)$. Then we use $2^n-1$ minus the two sets and we can get $S_{i,0}$. As the bounds may be large, we need to discrete it.

Total time complexity: $O(nlogn)$.

• +10

 » 9 months ago, # |   +3 You can avoid BIT by sorting the segments by starting points and ending points. code SpoilerEventhough the hash fucntion I used to hash $a_1, a_2, .. a_n$ is $\Pi (r + a_i)$. It will work for your hash function i.e, $\sum{a_i * r^i}$ too.
 » 9 months ago, # | ← Rev. 2 →   +6 To avoid hacks (and get a solution that is guaranteed to have a low probability of failure on any test) you can use a random base instead of 2.