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

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.

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.