# Mr. X and His Shots

# Mr. X and His Shots

+ 2 comments 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.

+ 1 comment 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())) print(solve(a,b,sorted(c),sorted(d)))

unreadable, but fun to write

+ 2 comments 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)

+ 1 comment 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[0] still returns 0 def binrank(ll,start,end,x): if start == end: return start mid = int(math.ceil((start+end)/2.)) if x >= ll[mid]: start = mid if x < ll[mid]: end = mid -1 return binrank(ll,start,end,x) def solve(shots, players): lshots = sorted([a[0] for a in shots]) rshots = sorted([a[1] for a in shots]) sl = len(lshots) scores = [] for (x,y) in players: if x-.5 < rshots[0]: miss1 = 0 else: miss1 = binrank(rshots,0,sl-1,x-.5) + 1 if y < lshots[0]: miss2 = 0 else: miss2 = sl-1 - binrank(lshots,0,sl-1,y) scores += [sl - (miss1+miss2)] return sum(scores)

+ 2 comments Just two binary searches are enough to solve. :)

Sort 47 Discussions, By:

Please Login in order to post a comment