Zonal Computing Olympiad 2012, 26 Nov 2011

The year is 2102 and today is the day of ZCO. This year there are N contests and the starting and ending times of each contest is known to you. You have to participate in exactly one of these contests. Different contests may overlap. The duration of different contests might be different. 

There is only one examination centre. There is a wormhole V that transports you from your house to the examination centre and another wormhole W that transports you from the examination centre back to your house. Obviously, transportation through a wormhole does not take any time; it is instantaneous. But the wormholes can be used at only certain fixed times, and these are known to you.

So, you use a V wormhole to reach the exam centre, possibly wait for some time before the next contest begins, take part in the contest, possibly wait for some more time and then use a W wormhole to return back home. If you leave through a V wormhole at time t1 and come back through a W wormhole at time t2, then the total time you have spent is (t2 - t1 + 1). Your aim is to spend as little time as possible overall while ensuring
that you take part in one of the contests.

You can reach the centre exactly at the starting time of the contest, if possible. And you can leave the examination centre the very second the contest ends, if possible. You can assume that you will always be able to attend at least one contest–that is, there will always be a contest such that there is a V wormhole before it and a W wormhole after it.

For instance, suppose there are 3 contests with (start,end) times (15,21), (5,10), and (7,25), respectively.  Suppose the V wormhole is available at times 4, 14, 25, 2 and the W wormhole is available at times 13 and 21.  In this case, you can leave by the V wormhole at time 14, take part in the contest from time 15 to 21, and then use the W wormhole at time 21 to get back home.  Therefore the time you have spent is (21 - 14 + 1) = 8. You can check that you cannot do better than this.

-----Input format-----
The first line contains 3 space separated integers N, X, and Y, where N is the number of contests, X is the number of time instances when wormhole V can be used and Y is the number of time instances when wormhole W can be used.  The next N lines describe each contest.  Each of these N lines contains two space separated integers S and E, where S is the starting time of the particular contest and E is the ending time of that contest, with S < E.  The next line contains X space separated integers which are the time instances when the wormhole V can be used.  The next line contains Y space separated integers which are the time instances when the wormhole W can be used.

-----Output format-----
Print a single line that contains a single integer, the minimum time needed to be spent to take part in a contest.

-----Testdata-----
All the starting and ending times of contests are distinct and no contest starts at the same time as another contest ends. The time instances when wormholes are available are all distinct, but may coincide with starting and ending times of contests. All the time instances (the contest timings and the wormhole timings) will be integers between 1 and 1000000 (inclusive).

- Subtask 1 (30 marks)
- Subtask 2 (70 marks)

You may assume that 
1 ≤ N ≤ 105,
1 ≤ X ≤ 105, and
1 ≤ Y ≤ 105.

In 30% of the cases, 
1 ≤ N ≤ 103,
1 ≤ X ≤ 103, and
1 ≤ Y ≤ 103.

-----Sample Input-----
3 4 2
15 21
5 10
7 25
4 14 25 2
13 21

-----Sample Output-----
8

Difficulty: interview

Starter code:

Solutions:
import sys
n, x, y = input().split(' ')
n = int(n)
x = int(x)
y = int(y)
contests = {}

for i in range(n):
 s, e = input().split(' ')
 s = int(s)
 e = int(e)
 contests[(s, e)] = abs(s-e)

v_time = input().split(' ')
w_time = input().split(' ')

v_time, w_time = list(map(int, v_time)), list(map(int, w_time))
v_time.sort()
w_time.sort()


score = sys.maxsize

contests = dict(sorted(contests.items(), key=lambda item: item[1]))
for k, v in contests.items():
 start=-1
 end = sys.maxsize
 for i in range(x):
  if v_time[i] > k[0]:
   break
  start = v_time[i]
 for j in range(y):
  if w_time[j] >= k[1]:
   end = w_time[j]
   break
 if start == -1:
  continue
 score = min(score, (end-start+1))
 if score-1 <= v:
  break

print(score)

# cook your dish here
import sys
import bisect
input=sys.stdin.readline
l=input().split()
n=int(l[0])
x=int(l[1])
y=int(l[2])
ok=[]
for i in range(n):
 l=input().split()
 li=[int(i) for i in l]
 ok.append(li)
l=input().split()
xi=[int(i) for i in l]
l=input().split()
yi=[int(i) for i in l]
xi.sort()
yi.sort()
mina=10**18
for i in range(n):
 num1=bisect.bisect_right(xi,ok[i][0])
 num2=bisect.bisect_left(yi,ok[i][1])
 if(num1>=1 and num2<y):
  mina=min(yi[num2]-xi[num1-1],mina)
print(mina+1)



import bisect
def wormholes(tlist,vlist,wlist):
 sumlist=[]
 for i in range(len(tlist)):
  if tlist[i][0] not in vlist:
   x=bisect.bisect_left(vlist,tlist[i][0])
   x=x-1
   if x<0:
    continue
  else:
   x=vlist.index(tlist[i][0])
  if tlist[i][1] not in wlist:
   y=bisect.bisect_right(wlist,tlist[i][1])
   if y>=len(wlist):
    continue
  else:
   y=wlist.index(tlist[i][1])
  sumlist.append(wlist[y]-vlist[x]+1)
 return min(sumlist)
n,x,y=input().split()
n,x,y=int(n),int(x),int(y)
timelist=[]
for i in range(n):
 s,e=input().split()
 s,e=int(s),int(e)
 timelist.append([s,e])
v=list(map(int,input().strip().split()))
w=list(map(int,input().strip().split()))
v.sort()
w.sort()
miv=min(v)
maw=max(w)
for i in range(n):
 if timelist[i][0]<miv or timelist[i][1]>maw:
  timelist[i]=[0,0]
while [0,0] in timelist:
 timelist.remove([0,0])
print(wormholes(timelist,v,w))


import bisect
def wormholes(tlist,vlist,wlist):
 sumlist=[]
 miv=min(vlist)
 maw=max(wlist)
 for i in range(len(tlist)):
  if tlist[i][0]<miv or tlist[i][1]>maw:
   continue
  if tlist[i][0] not in vlist:
   x=bisect.bisect_left(vlist,tlist[i][0])
   x=x-1
   if x<0:
    continue
  else:
   x=vlist.index(tlist[i][0])
  if tlist[i][1] not in wlist:
   y=bisect.bisect_right(wlist,tlist[i][1])
   if y>=len(wlist):
    continue
  else:
   y=wlist.index(tlist[i][1])
  sumlist.append(wlist[y]-vlist[x]+1)
 return min(sumlist)
n,x,y=input().split()
n,x,y=int(n),int(x),int(y)
timelist=[]
for i in range(n):
 s,e=input().split()
 s,e=int(s),int(e)
 timelist.append([s,e])
v=list(map(int,input().strip().split()))
w=list(map(int,input().strip().split()))
v.sort()
w.sort()
print(wormholes(timelist,v,w))


import bisect
def wormholes(tlist,vlist,wlist):
 sumlist=[]
 for i in range(len(tlist)):
  if tlist[i][0] not in vlist:
   x=bisect.bisect_left(vlist,tlist[i][0])
   x=x-1
   if x<0:
    continue
  else:
   x=vlist.index(tlist[i][0])
  if tlist[i][1] not in wlist:
   y=bisect.bisect_right(wlist,tlist[i][1])
   if y>=len(wlist):
    continue
  else:
   y=wlist.index(tlist[i][1])
  sumlist.append(wlist[y]-vlist[x]+1)
 return min(sumlist)
n,x,y=input().split()
n,x,y=int(n),int(x),int(y)
timelist=[]
for i in range(n):
 s,e=input().split()
 s,e=int(s),int(e)
 timelist.append([s,e])
v=list(map(int,input().strip().split()))
w=list(map(int,input().strip().split()))
v.sort()
w.sort()
print(wormholes(timelist,v,w))


import bisect
def wormholes(tlist,vlist,wlist):
 sumlist=[]
 for i in range(len(tlist)):
  if tlist[i][0] not in vlist:
   x=bisect.bisect_left(vlist,tlist[i][0])
   x=x-1
  else:
   x=vlist.index(tlist[i][0])
  if tlist[i][1] not in wlist:
   y=bisect.bisect_right(wlist,tlist[i][1])
  else:
   y=wlist.index(tlist[i][1])
  if y<len(wlist) and x>=0:
   sumlist.append(wlist[y]-vlist[x]+1)
 return min(sumlist)
n,x,y=input().split()
n,x,y=int(n),int(x),int(y)
timelist=[]
for i in range(n):
 s,e=input().split()
 s,e=int(s),int(e)
 timelist.append([s,e])
v=list(map(int,input().strip().split()))
w=list(map(int,input().strip().split()))
v.sort()
w.sort()
print((wormholes(timelist,v,w)))# cook your dish here


import bisect
def wormholes(tlist,vlist,wlist):
 sumlist=[]
 for i in range(len(tlist)):
  if tlist[i][0] not in vlist:
   x=bisect.bisect_left(vlist,tlist[i][0])
   x=x-1
  else:
   x=vlist.index(tlist[i][0])
  if tlist[i][1] not in wlist:
   y=bisect.bisect_right(wlist,tlist[i][1])
  else:
   y=wlist.index(tlist[i][1])
  if y<len(wlist) and x>=0:
   sumlist.append(wlist[y]-vlist[x]+1)
 return min(sumlist)
n,x,y=input().split()
n,x,y=int(n),int(x),int(y)
timelist=[]
for i in range(n):
 s,e=input().split()
 s,e=int(s),int(e)
 timelist.append([s,e])
v=list(map(int,input().strip().split()))
w=list(map(int,input().strip().split()))
v.sort()
w.sort()
print((wormholes(timelist,v,w)))# cook your dish here


# cook your dish here
def bs1(arr,x):
 low = 0 
 high = len(arr) - 1 
 p = 0 
 while(low<=high):
  mid = (low + high)//2
  if(arr[mid]==x):
   return arr[mid]
  elif(arr[mid]<x):
   p = mid
   low = mid + 1 
  else:
   high = mid - 1 
   
 if arr[p] <= x:
  return arr[p]
 else:
  return 0
 


def bs2(arr, x):
 low = 0 
 high = len(arr)-1 
 p = 0
 while(low<=high):
  mid = (low + high)//2 
  if(arr[mid]==x):
   return arr[mid]
  elif(arr[mid]<x):
   low = mid + 1 
  else:
   p = mid
   high = mid - 1 
 if arr[p] >= x:
  return arr[p]
 else:
  return 1000000
  


n,a,b = list(map(int,input().strip().split()))
s = []
e = []
for i in range(n):
 c,d = list(map(int,input().strip().split()))
 s.append(c)
 e.append(d)
ws = list(map(int,input().strip().split()))
vs = list(map(int,input().strip().split()))
ws.sort()
vs.sort()
r = 1000000
for i in range( n):
 s1 = bs1(ws,s[i])
 e1 = bs2(vs,e[i])
 r1 = e1-s1+1 
 if(r1<r):
  r = r1
print(r)

# cook your dish here
n,a,b = list(map(int,input().strip().split()))
s = []
e = []
for i in range(n):
 c,d = list(map(int,input().strip().split()))
 s.append(c)
 e.append(d)
ws = list(map(int,input().strip().split()))
vs = list(map(int,input().strip().split()))
ws.sort(reverse = True)
vs.sort()
r = 1000000
for i in range( n):
 s1 = 0
 e1 = 1000000
 for j in range(a):
  if(ws[j]<=s[i]):
   s1 = ws[j]
   break
 for j in range(b):
  if(vs[j]>=e[i]):
   e1 = vs[j]
   break
 r1 = e1-s1+1 
 if(r1<r):
  r = r1
print(r)

# cook your dish here
n, v, w = list(map(int,input().strip().split()))
s = []
e = []
for i in range(n):
 o, u = list(map(int,input().strip().split()))
 s.append(o)
 e.append(u)
vs = list(map(int,input().strip().split()))
ws = list(map(int,input().strip().split()))
vs.sort()
ws.sort()
r = 1000000
for i in range(n):
 s1 = 0 
 e1 = 1000000
 for j in vs:
  if(s[i]>= j):
   s1 = j 
  else:
   break
 for j in range(len(ws)-1,-1,-1):
  if(e[i]<= ws[j]):
   e1 = ws[j]
  else:
   break
 r1 = e1 - s1 + 1
 if(r1<r):
  r = r1
print(r)
 
   



# cook your dish here
import sys
import bisect
input=sys.stdin.readline
l=input().split()
n=int(l[0])
x=int(l[1])
y=int(l[2])
ok=[]
for i in range(n):
 l=input().split()
 li=[int(i) for i in l]
 ok.append(li)
l=input().split()
xi=[int(i) for i in l]
l=input().split()
yi=[int(i) for i in l]
xi.sort()
yi.sort()
mina=10**18
for i in range(n):
 num1=bisect.bisect_right(xi,ok[i][0])
 num2=bisect.bisect_left(yi,ok[i][1])
 if(num1>=1 and num2<y):
  mina=min(yi[num2]-xi[num1-1],mina)
print(mina+1)


import itertools
# cook your dish here

N, X, Y = list(map(int, input().split()))
contests = []
for _ in range(N):
 contests.append(list(map(int, input().split())))

into = list(map(int, input().split()))
outo = list(map(int, input().split()))

 
worthwole = [(x,y) for x, y in itertools.product(into, outo) if x < y]
worthwole = sorted(worthwole, key = lambda x : x[1] - x[0])
# print(worthwole)

result = 0
found = False
for w in worthwole:
 for c in contests : 
  if w[0] <= c[0] and w[1] >= c[1] : 
   result = w[1] - w[0] + 1
   found = True
   break
 
 if found : break

print(result)


# cook your dish here
import sys
from operator import itemgetter
n, x, y = map(int, input().strip().split())
tests=[]
for _ in range(n):
 start, end = map(int, input().strip().split())
 tests.append([start,end,1+end-start])
start=[]
start[:]=map(int, input().strip().split())
start.sort()
end=[]
end[:]=map(int, input().strip().split())
end.sort()
tests.sort(key=itemgetter(0))
while tests[0][0]<start[0]:
 tests.pop(0)
 n-=1
j=0
for i in range(n):
 while j<x-1 and start[j+1]<=tests[i][0]:
  j+=1
 tests[i][2]+=tests[i][0]-start[j]
tests.sort(key=itemgetter(1))
while tests[-1][1]>end[-1]:
 tests.pop()
 n-=1
j=y-1
for i in range(n-1,-1,-1):
 while j>0 and end[j-1]>=tests[i][1]:
  j-=1
 tests[i][2]+=end[j]-tests[i][1]
minimo=tests[0][2]
for i in range(n):
 minimo=min(minimo, tests[i][2])
print(minimo)

nk = [int(i) for i in input().split()]
n = nk[0]
x = nk[1]
y = nk[2]
contests = []
time = []
while n > 0 :
 contests.append([int(i) for i in input().split()])
 n = n - 1
n = nk[0]
vworm = [int(i) for i in input().split()]
wworm = [int(i) for i in input().split()]
vworm.sort(reverse=True)
wworm.sort()
t1=0
t2=0
mint = 10**6

for contest in contests :
  if contest[1] - contest[0] > mint :
   continue

  t1 =0
  for vbus in vworm :
   if vbus <= contest[0] :
    t1 = vbus
    break

  t2=0
  for wbus in wworm :
   if wbus >= contest[1]:
    t2 = wbus
    break

  if t1 > 0 and t2 > 0 and t2 >= t1:
   t = t2 - t1 + 1
   if t <= mint  :
    mint = t


print(mint)


# cook your dish here
def ub(arr,item):
 n=len(arr)
 low=0;high=n-1
 while low<=high:
  mid=low+(high-low)//2
  if arr[mid]==item:
   return mid
  elif arr[mid]<item:
   low=mid+1
  else:
   high=mid-1
 
 return low


def lb(arr,item):
 low=0;high=len(arr)-1
 while low<=high:
  mid=low+(high-low)//2
  if arr[mid]==item:
   return mid
  elif arr[mid]<item:
   low=mid+1
  else:
   high=mid-1
 return high

def main():
 n,x,y=map(int,input().split())
 timing=[]
 for i in range(n):
  p,q=map(int,input().split())
  timing.append((p,q))
  
  

 v=list(map(int,input().split()))

 w=list(map(int,input().split()))
 timing.sort()
 v.sort()
 w.sort()

 mn=1e18
 

 for i in range(n):
  s=lb(v,timing[i][0])
  e=ub(w,timing[i][1])
  if s>=0 and e<y:
   mn=min(mn,abs(v[s]-w[e])+1)
  
 print(mn)
main()

# cook your dish here
def ub(arr,item):
 n=len(arr)
 low=0;high=n-1
 while low<=high:
  mid=low+(high-low)//2
  if arr[mid]==item:
   return mid
  elif arr[mid]<item:
   low=mid+1
  else:
   high=mid-1
 
 return low


def lb(arr,item):
 low=0;high=len(arr)-1
 while low<=high:
  mid=low+(high-low)//2
  if arr[mid]==item:
   return mid
  elif arr[mid]<item:
   low=mid+1
  else:
   high=mid-1
 return high

def main():
 n,x,y=list(map(int,input().split()))
 timing=[]
 for i in range(n):
  p,q=list(map(int,input().split()))
  timing.append((p,q))
  
  

 v=list(map(int,input().split()))

 w=list(map(int,input().split()))
 timing.sort()
 v.sort()
 w.sort()

 mn=1e18
 

 for i in range(n):
  s=lb(v,timing[i][0])
  e=ub(w,timing[i][1])
  if s>=0 and e<y:
   mn=min(mn,abs(v[s]-w[e])+1)
  
 print(mn)
main()
     
    
   
    



def ub(arr,item):
 n=len(arr)
 low=0;high=n-1
 while low<=high:
  mid=low+(high-low)//2
  if arr[mid]==item:
   return mid
  elif arr[mid]<item:
   low=mid+1
  else:
   high=mid-1
 
 return low


def lb(arr,item):
 low=0;high=len(arr)-1
 while low<=high:
  mid=low+(high-low)//2
  if arr[mid]==item:
   return mid
  elif arr[mid]<item:
   low=mid+1
  else:
   high=mid-1
 return high

def main():
 n,x,y=list(map(int,input().split()))
 timing=[]
 for i in range(n):
  p,q=list(map(int,input().split()))
  timing.append((p,q))
  
  

 v=list(map(int,input().split()))

 w=list(map(int,input().split()))
 timing.sort()
 v.sort()
 w.sort()

 mn=1e18
 

 for i in range(n):
  s=lb(v,timing[i][0])
  e=ub(w,timing[i][1])
  if s>=0 and e<y:
   mn=min(mn,abs(v[s]-w[e])+1)
  
 print(mn)
main()
     
    
   
    


# cook your dish here
from sys import stdin, stdout
import math


def lower_bound(arr, ele):
 low = 0
 high = len(arr)-1
 while low <= high:
  mid = (low+high)//2
  if arr[mid] == ele:
   return arr[mid]
  elif ele < arr[mid]:
   high = mid-1
  else:
   low = mid+1
 if high > len(arr)-1 or high < 0:
  return -1
 return arr[high]


def upper_bound(arr, ele):
 low = 0
 high = len(arr)-1
 while low <= high:
  mid = (low+high)//2
  if arr[mid] == ele:
   return arr[mid]
  elif ele < arr[mid]:
   high = mid-1
  else:
   low = mid+1
 if low > len(arr)-1 or low < 0:
  return -1
 return arr[low]


def main():
 n, n_x, n_y = list(map(int, stdin.readline().split()))
 contests = [None]*n
 for i in range(n):
  start, end = list(map(int, stdin.readline().split()))
  contests[i] = (start, end)
 V = [int(x) for x in stdin.readline().split()]
 W = [int(x) for x in stdin.readline().split()]
 V.sort()
 W.sort()
 ans = math.inf
 for (start, end) in contests:
  opv = lower_bound(V, start)
  opw = upper_bound(W, end)
  if opv == -1 or opw == -1:
   continue
  ans = min(ans, opw - opv + 1)
 print(ans)


def __starting_point():
 main()

__starting_point()