tzc_wk's blog

By tzc_wk, history, 9 months ago, In English

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)$$$.

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can avoid BIT by sorting the segments by starting points and ending points. code

Spoiler
»
9 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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.