You are given two non-empty arrays A and B consisting of N integers. These arrays represent N planks. More precisely, A[K] is the start and B[K] the end of the K−th plank.
Next, you are given a non-empty array C consisting of M integers. This array represents M nails. More precisely, C[I] is the position where you can hammer in the I−th nail.
We say that a plank (A[K], B[K]) is nailed if there exists a nail C[I] such that A[K] ≤ C[I] ≤ B[K].
The goal is to find the minimum number of nails that must be used until all the planks are nailed. In other words, you should find a value J such that all planks will be nailed after using only the first J nails. More precisely, for every plank (A[K], B[K]) such that 0 ≤ K < N, there should exist a nail C[I] such that I < J and A[K] ≤ C[I] ≤ B[K].
For example, given arrays A, B such that:
A[0] = 1 B[0] = 4 A[1] = 4 B[1] = 5 A[2] = 5 B[2] = 9 A[3] = 8 B[3] = 10four planks are represented: [1, 4], [4, 5], [5, 9] and [8, 10].
Given array C such that:
C[0] = 4 C[1] = 6 C[2] = 7 C[3] = 10 C[4] = 2if we use the following nails:
- 0, then planks [1, 4] and [4, 5] will both be nailed.
- 0, 1, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, then planks [1, 4], [4, 5] and [5, 9] will be nailed.
- 0, 1, 2, 3, then all the planks will be nailed.
Thus, four is the minimum number of nails that, used sequentially, allow all the planks to be nailed.
Write a function:
def solution(A, B, C)
that, given two non-empty arrays A and B consisting of N integers and a non-empty array C consisting of M integers, returns the minimum number of nails that, used sequentially, allow all the planks to be nailed.
If it is not possible to nail all the planks, the function should return −1.
For example, given arrays A, B, C such that:
A[0] = 1 B[0] = 4 A[1] = 4 B[1] = 5 A[2] = 5 B[2] = 9 A[3] = 8 B[3] = 10 C[0] = 4 C[1] = 6 C[2] = 7 C[3] = 10 C[4] = 2the function should return 4, as explained above.
Write an efficient algorithm for the following assumptions:
- N and M are integers within the range [1..30,000];
- each element of arrays A, B and C is an integer within the range [1..2*M];
- A[K] ≤ B[K].
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C))
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C))
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [1, 1, 1]]
Traceback (most recent call last): File "user.py", line 158, in <module> result = solution ( A, B, C ) File "user.py", line 40, in solution r.update(C[idx], idx) File "user.py", line 11, in update if self.dat[idx] < x: IndexError: list index out of range
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C))
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [1, 1, 1]]
WARNING: producing output may seriously slow down your code!stdout:
19 0 21 1 22 2 25 3 17 4
Traceback (most recent call last): File "user.py", line 159, in <module> result = solution ( A, B, C ) File "user.py", line 41, in solution r.update(C[idx], idx) File "user.py", line 12, in update if self.dat[idx] < x: IndexError: list index out of rangestdout:
1 0
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C))
print r
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [1, 1, 1]]
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 16 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 19 0 21 1 22 2 25 3 17 4
Traceback (most recent call last): File "user.py", line 160, in <module> result = solution ( A, B, C ) File "user.py", line 42, in solution r.update(C[idx], idx) File "user.py", line 12, in update if self.dat[idx] < x: IndexError: list index out of rangestdout:
RMQ of size 1 with [2147483647] 1 0
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(max(C), 4))
print r
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [1, 1, 1]]
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 16 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 19 0 21 1 22 2 25 3 17 4
function result: 1
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 4 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 4 0 4 1 4 2
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(max(C), 4))
print r
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [5]]
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 16 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 19 0 21 1 22 2 25 3 17 4
function result: 1
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 8 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 12 0
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(max(C), 2))
print r
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [5]]
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 16 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 19 0 21 1 22 2 25 3 17 4
function result: 1
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 8 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 12 0
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ((max(C)+1)
print r
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [5]]
File "user.py", line 40 print r ^ SyntaxError: invalid syntax
File "user.py", line 40 print r ^ SyntaxError: invalid syntax
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C)+1)
print r
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [5]]
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 16 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 19 0 21 1 22 2 25 3 17 4
function result: 1
WARNING: producing output may seriously slow down your code!stdout:
RMQ of size 8 with [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647] 12 0
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C)+1)
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [5]]
WARNING: producing output may seriously slow down your code!stdout:
19 0 21 1 22 2 25 3 17 4
function result: 1
WARNING: producing output may seriously slow down your code!stdout:
12 0
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
print idx, x
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C)+1)
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [1, 1, 1]]
WARNING: producing output may seriously slow down your code!stdout:
19 0 21 1 22 2 25 3 17 4
function result: 1
WARNING: producing output may seriously slow down your code!stdout:
2 0 2 1 2 2
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C)+1)
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [1, 1, 1]]
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C)+1)
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
[[1], [5], [1, 1, 1]]
import math
class RMQ:
def __init__(self, n):
self.sz = 1
self.inf = (1 << 31) - 1
self.sz = (1 << int(math.ceil(math.log(n) / math.log(2))))
self.dat = [self.inf] * (2 * self.sz - 1)
def update(self, idx, x):
idx += self.sz - 1
if self.dat[idx] < x:
return
self.dat[idx] = x
while idx > 0:
idx = (idx - 1) >> 1
self.dat[idx] = min(self.dat[idx * 2 + 1], self.dat[idx * 2 + 2])
def fill(self, A):
for index,value in enumerate(A):
self.update(index,(value, index))
def query(self, a, b):
return self.query_help(a, b, 0, 0, self.sz)
def query_help(self, a, b, k, l, r):
if r <= a or b <= l:
return self.inf
elif a <= l and r <= b:
return self.dat[k]
else:
return min(self.query_help(a, b, 2 * k + 1, l, (l + r)>>1),
self.query_help(a, b, 2 * k + 2, (l + r) >> 1, r))
def __str__(self):
return "RMQ of size " + str(self.sz) + " with " + str(self.dat)
def solution(A, B, C):
r = RMQ(max(C)+1)
for idx in xrange(len(C)):
r.update(C[idx], idx)
min_nail_idx = 0
for idx in xrange(len(A)):
min_nail_idx = max(min_nail_idx, r.query(A[idx], B[idx]+1))
if min_nail_idx == r.inf:
return -1
else:
return min_nail_idx+1
The solution obtained perfect score.