Sort 47 Discussions, By:
Please Login in order to post a comment
I solved this using two binary indexed trees, longest running time being 0.28s. Let [L1,R1], [L2,R2] be intervals, with L1 <= R1, L2 <= R2. To check whether they overlap or not, we simply check if ((R2 < L1) || (L2 > R1)) holds. If this is true, then they are NOT overlapping, otherwise they overlap.
Let the set of all N intervals be given, say [A1,B1] ... [AN,BN], for each player interval [C,D] we want to count the number of NON-overlapping intervals from [Ai,Bi]'s, then the overlap count can be incremented by (N - (non-overlapping count)). We can use a binary indexed tree to preprocess the [Ai,Bi]'s to store the number of Bi's occurred BEFORE a given position, and another BIT tree for the number of Ai's occurring AFTER a given position.
Then, when the player interval [C,D] is given, simply use the BIT trees above to determine the number of Ai's greater then D, and the number of Bi's less then C.
four lines in python3
from bisect import bisect_left, bisect_right
def solve(a,b,c,d): return sum(bisect_right(c,v) for v in b)-sum(bisect_left(d,u) for u in a)
(a,b),(c,d)=(zip(*(map(int,input().split()) for _ in range (k))) for k in map(int,input().split()))
unreadable, but fun to write
Initially I tried using an interval tree, but it was too slow and timed out.
I found a completely different approach that works well and is O((n+m) log (n+m)). Treat the start and ends of intervals as events, and the values as time. Starting from the earliest time first, look at each event, and adjust the number of shots, players, and the result accordingly. There are 4 different types of events to handle:
1. X interval starts
2. X interval ends
3. player interval starts
4. player interval ends
(hint: make sure you handle ending events after starting events if you have multiple events occuring at the same time)
The same idea: counting misses with a binary search. But I am using a trick (see the x-.5) to treat the cases where the endpoints match. It only works because the intervals are all integers but I couldn't see how to do it more elegantly.
# For list ll sorted lowest first, binrank(ll,0,len(ll)-1,x)
# = largest index i such that ll[i] <= x
# BUT If x < ll still returns 0
if start == end:
mid = int(math.ceil((start+end)/2.))
if x >= ll[mid]:
start = mid
if x < ll[mid]:
end = mid -1
def solve(shots, players):
lshots = sorted([a for a in shots])
rshots = sorted([a for a in shots])
sl = len(lshots)
scores = 
for (x,y) in players:
if x-.5 < rshots:
miss1 = 0
miss1 = binrank(rshots,0,sl-1,x-.5) + 1
if y < lshots:
miss2 = 0
miss2 = sl-1 - binrank(lshots,0,sl-1,y)
scores += [sl - (miss1+miss2)]
Just two binary searches are enough to solve. :)