Problem:

Range Minimum Query (RMQ)

Write a program which manipulates a sequence A = {a0, a1, . . .  , an-1} with the following operations:

find(s, t): report the minimum element in as, as+1, . . . ,at.

update(i, x): change ai to x.

Note that the initial values of ai (i = 0, 1, . . .  , n&minus;1) are  231-1.

Input

n q
com0 x0 y0
com1 x1 y1
...
comq&minus;1 xq&minus;1 yq&minus;1

In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, q queries are given where com represents the type of queries. '0' denotes update(xi, yi) and '1' denotes find(xi, yi).

Output

For each find operation, print the minimum element.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

If comi is 0, then 0 ≤ xi < n, 0 ≤ yi < 231-1.

If comi is 1, then 0 ≤ xi < n, 0 ≤ yi < n.

Sample Input 1

3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2

Sample Output 1

1
2

Sample Input 2

1 3
1 0 0
0 0 5
1 0 0

Sample Output 2

2147483647
5



Sample input:
3 5
0 0 1
0 1 2
0 2 3
1 0 2
1 1 2


Sample output:
1
2

Submission status: Wrong Answer

Solution code:
import math

def update(index,n):
    targ[index] = n
    index = (index - 1) // 2
    while True:
        targ[index] = min(targ[index * 2 + 1],targ[index * 2 + 2])
        if index <= 0:
            break
        index = (index - 1) // 2

def find(i,e,node,inode,enode):
    #print(i,e,node,inode,enode)
    if inode > e or enode < i:
        return float("inf")
    elif (i <= inode and enode <= e) or inode==enode:
        return targ[node]

    else:
        irange = find(i,e,2*node + 1,inode,(inode+enode)// 2 )
        erange = find(i,e,2*node + 2,(inode+enode)//2 + 1,enode)
        return min(irange,erange)

num,query = (int(n) for n in input().split(' '))
initial = 2147483647
ln = 2 ** math.ceil(math.log2(num)) - 1
if num == 1:
    tail = 2
else:
    tail = 2 ** math.ceil(math.log2(num)) - num
global targ
targ = [initial] * (ln + num + tail)
length = num - 1

for q in range(query):
    #print(targ)
    temp = [int(n) for n in input().split(' ') ]
    if temp[0] == 0:
        update(temp[1] + ln,temp[2])
    else:
        print(find(temp[1],temp[2],0,0,length))

Submission status: Wrong Answer

Solution code:
def update(i, x):
    i += base
    while i>0:
        st[i] = min(st[i], x)
        i//=2


def find(a, b):
    return _find(a, b+1, 0, 0, n)


def _find(a, b, k, l, r):
    if b <= l or r <= a:
        return 2**31-1

    if a <= l and r <= b:
        return st[k]

    rl = _find(a, b, 2*k+1, l, (l+r)/2)
    rr = _find(a, b, 2*k+2, (l+r)/2, r)
    return min(rl, rr)


(_n, q) = map(int, input().split())

n=1
while(n<=_n):
    n *= 2
base = n-1
st = [2**31-1]*(2*n-1)

for i in range(q):
    (c, l, r) = map(int, input().split())
    if c:
        print(find(l, r))
    else:
        update(l, r)

Submission status: Wrong Answer

Solution code:
def update(i, x):
    i += base
    st[i] = x
    while i>0:
        i//=2
        st[i] = min(st[i*2+1], st[i*2+2])


def find(a, b):
    return _find(a, b+1, 0, 0, n)


def _find(a, b, k, l, r):
    if b <= l or r <= a:
        return 2**31-1

    if a <= l and r <= b:
        return st[k]

    rl = _find(a, b, 2*k+1, l, (l+r)/2)
    rr = _find(a, b, 2*k+2, (l+r)/2, r)
    return min(rl, rr)


(_n, q) = map(int, input().split())

n=1
while(n<=_n):
    n *= 2
base = n-1
st = [2**31-1]*(2*n-1)

for i in range(q):
    (c, l, r) = map(int, input().split())
    if c:
        print(find(l, r))
    else:
        update(l, r)

Submission status: Wrong Answer

Solution code:
dat = []

def init(n):
  global dat
  k = 1
  while (k < n):
    k = k * 2
  n = k
  dat = [2**31 - 1 for i in range(2 * k - 1)]

def update(k, y):
  global dat
  k += n - 1
  dat[k] = y;
  while (k > 0):
    k = int((k - 1) / 2)
    dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2])

def query(a, b, k, l, r):
  if (r <= a or b <= l):
    return 2**31 - 1
  if (a <= l and r <= b):
    return dat[k]
  
  vl = query(a, b, k * 2 + 1, l, int((l + r) / 2))
  vr = query(a, b, k * 2 + 2, int((l + r / 2)), r)

  return min(vl, vr)

# main
n, q = map(int, input().split())

init(n)

for i in range(q):
  com, x, y = map(int, input().split())
  if com == 0:
    update(x, y)
  else:
    
    print(query(x, y+1, 0, 0, n))

Submission status: Wrong Answer

Solution code:
dat = []

def init(n):
  global dat
  k = 1
  while (k < n):
    k = k * 2
  n = k
  dat = [2**31 - 1 for i in range(2 * k - 1)]

def update(k, y):
  global dat
  k += n - 1
  dat[k] = y;
  while (k > 0):
    k = int((k - 1) / 2)
    dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2])

def query(a, b, k, l, r):
  if (r <= a or b <= l):
    return 2**31 - 1
  if (a <= l and r <= b):
    return dat[k]
  
  vl = query(a, b, k * 2 + 1, l, (l + r) // 2)
  vr = query(a, b, k * 2 + 2, (l + r) // 2, r)

  return min(vl, vr)

# main
n, q = map(int, input().split())

init(n)

for i in range(q):
  com, x, y = map(int, input().split())
  if com == 0:
    update(x, y)
  else:
    
    print(query(x, y+1, 0, 0, n))

Submission status: Wrong Answer

Solution code:
def updt(lst, i, x):
    lst[i] = x


def fnd(lst, s, t):
    m = min(lst[s:t+1])
    if m == 0:
        return 2**31 -1
    return m


def rmq():
    n, q = map(int, input().split())
    A = [x for x in range(n)]
    ans = []
    for _ in range(q):
        cmd, x, y = map(int, input().split())
        if cmd == 0:
            updt(A, x, y)
        else:
            ans.append(fnd(A, x, y))
    print(*ans, sep="\n")


if __name__ == "__main__":
    rmq()

Submission status: Wrong Answer

Solution code:
def updt(lst, i, x):
    lst[i] = x


def fnd(lst, s, t):
    m = min(lst[s:t+1])
    if m == 0:
        return 2**31 -1
    return m


def rmq():
    n, q = map(int, input().split())
    A = [0 for _ in range(n)]
    ans = []
    for _ in range(q):
        cmd, x, y = map(int, input().split())
        if cmd == 0:
            updt(A, x, y)
        else:
            ans.append(fnd(A, x, y))
    print(*ans, sep="\n")


if __name__ == "__main__":
    rmq()

Submission status: Wrong Answer

Solution code:
import sys


def updt(lstv, lstk, i, x):
    lstv[i] = x
    lstk[i] = i


def fnd(lstv, lstk, s, t):
        if max(lstk[s:t+1]) == -1:
            return -1
        else:
            m = 2**31 -1
            for k in lstk[s:t+1]:
                if k >= 0:
                    if m > lstv[k]:
                        m = lstv[k]
            return m

def rmq():
    n, q = map(int, sys.stdin.readline().split())
    Av = [0 for _ in range(n)]
    Ak = [-1 for _ in range(n)]
    ans = []
    for _ in range(q):
        cmd, x, y = map(int, sys.stdin.readline().split())
        if cmd == 0:
            updt(Av, Ak, x, y)
        else:
            ans.append(fnd(Av, Ak, x, y))
    for an in ans:
        if an == -1:
            print(2**31 -1, sep="\n")
        else:
            print(an, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys


def updt(lstv, lstk, i, x):
    lstv[i] = x
    lstk[i] = i


def fnd(lstv, lstk, s, t):
        if max(lstk[s:t+1]) == -1:
            return 2**31 -1
        else:
            m = 2**31 -1
            li = lstk[s:t+1]
            if 0 in li:
                return 0
            for k in li:
                if k > 0:
                    if m > lstv[k]:
                        m = lstv[k]
            return m

def rmq():
    n, q = map(int, sys.stdin.readline().split())
    Av = [0 for _ in range(n)]
    Ak = [-1 for _ in range(n)]
    ans = []
    for _ in range(q):
        cmd, x, y = map(int, sys.stdin.readline().split())
        if cmd == 0:
            updt(Av, Ak, x, y)
        else:
            ans.append(fnd(Av, Ak, x, y))
    print(*ans, sep="\n")


if __name__ == "__main__":
    rmq()

Submission status: Wrong Answer

Solution code:
import math, sys

#??°????????????????????§????°????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [0] * (2 * self.TreeRange - 1)

    def add(self, i, x):
        i += self.TreeRange - 1
        self.List[i] += x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] += x

    def getsum(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°0????????????
        if right <= s or t <= left:
            return 0
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.getsum(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.getsum(s, t, i * 2 + 2, (left + right) // 2, right)
            return l + r

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.add(x - 1, y)
    elif cmd == 1:
        print(ST.getsum(x - 1,y , right = ST.TreeRange))

Submission status: Wrong Answer

Solution code:
class RMQ:

    def __init__(self, length):
        import math
        self.length = 2 ** math.ceil(math.log(length, 2))
        self.segtree = [float("inf")] * (2 ** (self.length + 1) - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if b <= l or r <= a:
            return float("inf")
        elif a <= l <= r <= b:
            return self.segtree[index]
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length))

Submission status: Wrong Answer

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length <= length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b or a == b:
            return self.segtree[index]
        if b <= l or r <= a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length))

Submission status: Wrong Answer

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b or a == b:
            return self.segtree[self.length - 1 + index]
        elif a == b:
            return self.segtree[a]
        elif b <= l or r <= a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length))

Submission status: Wrong Answer

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a <= l <= r <= b or a == b:
            return self.segtree[self.length - 1 + index]
        elif a == b:
            return self.segtree[a]
        elif b <= l or r <= a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))

Submission status: Wrong Answer

Solution code:
class RMQ:
    def __init__(self, length, ini_num = float("inf")):
        self.length = 1
        while self.length < length:
            self.length <<= 1
        self.segtree = [ini_num] * (2 * self.length - 1)

    def update(self, index, n):
        leaf_index = index + self.length - 1
        self.segtree[leaf_index] = n
        while leaf_index > 0:
            leaf_index = (leaf_index - 1) // 2
            self.segtree[leaf_index] = min(self.segtree[leaf_index * 2 + 1], self.segtree[leaf_index * 2 + 2])

    def find(self, a, b, index, l, r):
        if a == b:
            return self.segtree[self.length - 1 + a] 
        elif a <= l <= r <= b:
            return self.segtree[index]
        elif b <= l or r <= a:
            return float("inf")
        else:
            return min(self.find(a, b, index * 2 + 1, l, (l + r) // 2), self.find(a, b, index * 2 + 2, (l + r) // 2, r))

v_num, query = (int(n) for n in input().split(" "))
rmq = RMQ(v_num, 2147483647)
for _ in range(query):
    com, i, n = (int(n) for n in input().split(" ") )
    if com == 0:
        rmq.update(i, n)
    else:
        print(rmq.find(i, n, 0, 0, rmq.length - 1))

Submission status: Wrong Answer

Solution code:
class SegmentTree():
	def __init__(self,n):
		self.dat = [INF for _ in range(n*2-1)]
		#index n???????????????????????¢?????????:
		#???????????? : (n-1)//2
		#???????????? : (2n+1) , (2n+2)
		self.n = n

	def update (self,node_index,value):
		""" index?????????value????????´?????? """
		index = node_index + (self.n-1) #node_index????????????dot???index?????????
		self.dat[index] = value

		#?????°????????????????????????????????´????????????
		while index > 0 :
			index = (index - 1) // 2				 #???????????????????????£???
			self.dat[index] = min([self.dat[index*2+1],self.dat[index*2+2]]) #??????????????????????????????

	def querry (self,left,right,nowNode,nowLeft,nowRight):
		"""[left,right):??¢?´¢??????,noeNode:?????¨????????????,[nowLeft,nowRight):?????¨?????????????????????"""

		# ??????????????¶??£????????????
		if nowRight < left or nowLeft > right:
			return INF

		# ?????¨?????¢?´¢???????????¨????????????????????????????????????
		if left <= nowLeft and nowRight <= right:
			return self.dat[nowNode]

		# ???????????????????????????????????¨???????????????
		else:
			value_left =self.querry(left,right,2*nowNode+1,nowLeft,(nowLeft+nowRight)//2)
			value_right = self.querry(left,right,2*nowNode+2,(nowLeft+nowRight)//2+1,nowRight)
			return min([value_left,value_right])

	def DEBUG_dat(self):
		print(self.dat)
		

if __name__ == "__main__":
	# ??????????????????
	INF = float('inf')
	n ,q  = map(int,input().split(" "))

	for i in range(1,9):
		if 2 ** i >= n:
			min_pow2 = 2 **  i
			break

	tree = SegmentTree(min_pow2)

	for i in range(q):
		com,x,y = map(int,input().split(" "))
		if com == 0:
			tree.update(x,y)
		else:
			print(tree.querry(x,y,0,0,min_pow2-1))

Submission status: Wrong Answer

Solution code:
class SegmentTree():
	def __init__(self,n):
		self.dat = [INF for _ in range(n*2-1)]
		#index n???????????????????????¢?????????:
		#???????????? : (n-1)//2
		#???????????? : (2n+1) , (2n+2)
		self.n = n

	def update (self,node_index,value):
		""" index?????????value????????´?????? """
		index = node_index + (self.n-1) #node_index????????????dot???index?????????
		self.dat[index] = value

		#?????°????????????????????????????????´????????????
		while index > 0 :
			index = (index - 1) // 2				 #???????????????????????£???
			self.dat[index] = min([self.dat[index*2+1],self.dat[index*2+2]]) #??????????????????????????????

	def querry (self,left,right,nowNode,nowLeft,nowRight):
		"""[left,right):??¢?´¢??????,noeNode:?????¨????????????,[nowLeft,nowRight):?????¨?????????????????????"""

		# ??????????????¶??£????????????
		if nowRight < left or nowLeft > right:
			return INF

		# ?????¨?????¢?´¢???????????¨????????????????????????????????????
		if left <= nowLeft and nowRight <= right:
			return self.dat[nowNode]

		# ???????????????????????????????????¨???????????????
		else:
			value_left =self.querry(left,right,2*nowNode+1,nowLeft,(nowLeft+nowRight)//2)
			value_right = self.querry(left,right,2*nowNode+2,(nowLeft+nowRight)//2+1,nowRight)
			return min([value_left,value_right])

	def DEBUG_dat(self):
		print(self.dat)
		

if __name__ == "__main__":
	# ??????????????????
	INF = float('inf')
	n ,q  = map(int,input().split(" "))

	for i in range(1,9):
		if 2 ** i >= n:
			min_pow2 = 2 **  i
			break

	tree = SegmentTree(min_pow2)

	for i in range(q):
		com,x,y = map(int,input().split(" "))
		if com == 0:
			tree.update(x,y)
		else:
			print(tree.querry(x,y,0,0,min_pow2-1))

Submission status: Wrong Answer

Solution code:
# Range Mininum Query
# 平方分割
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
import math
MAX = int(math.pow(2,31)-1)

par = [int(item) for item in input().split()]
span = math.ceil(math.sqrt(par[0]))
data = [MAX for i in range(par[0])]
backet = [MAX for i in range(span)]

def update(i, x):
    data[i] = x
    if backet[int(i/span)] > x:
        backet[int(i/span)] = x

def minimum(x, y):
    b_min = math.ceil(x/span)
    b_max = math.floor(y/span)
    #print("x: " + str(x) + " y: "+str(y))
    #print("backet from: " + str(b_min) + " to:" +str(b_max))
    result = MAX
    for i in range(x, b_min * span):
        if data[i] < result:
             result = data[i]
    for i in range(b_min, b_max+1):
        if backet[i] < result:
             result = backet[i]
    for i in range(b_max * span, y+1):
        if data[i] < result:
             result = data[i]

    return result


for i in range(par[1]):
    line = [int(item) for item in input().split()]
    if line[0] == 0:
        update(line[1], line[2])
    else:
        print(minimum(line[1], line[2]))

Submission status: Wrong Answer

Solution code:
# Range Mininum Query
# 平方分割
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
import math
import functools as ft
MAX = int(math.pow(2,31)-1)

par = [int(item) for item in input().split()]
span = math.floor(math.sqrt(par[0]))
data = [MAX for i in range(par[0])]
backet = [MAX for i in range(math.ceil(par[0]/span))]

def dump_data():
    print(" === DEBUG === ")
    print("DATA:\t" + ft.reduce(lambda x, y: x + str(y) + " ", data, "") )
    print("BACKET:\t" + ft.reduce(lambda x, y: x + str(y) + " ", backet, "") )

def update(i, x):
    data[i] = x
    result = MAX
    buf = int(i/span)
    for i in range(span):
        if buf * span + i >= par[0]:
            break
        if data[buf * span + i] < result:
            result = data[buf * span + i]
    backet[buf] = result


# 0 1 2 3 4 5 6 7 8 9

def minimum(x, y):
    b_min = math.ceil(x/span)
    b_max = max(int(y/span), int((y+1)/span))
    #print("x: " + str(x) + " y: "+str(y))
    #print("backet from: " + str(b_min) + " to:" +str(b_max))
    result = MAX

    for i in range(x, b_min * span):
        if data[i] < result:
             result = data[i]
    for i in range(b_min, b_max):
        if backet[i] < result:
             result = backet[i]
    for i in range(b_max * span, y+1):
        if data[i] < result:
             result = data[i]

    return result


for i in range(par[1]):
    #dump_data()
    line = [int(item) for item in input().split()]
    if line[0] == 0:
        update(line[1], line[2])
    else:
        print(minimum(line[1], line[2]))

Submission status: Wrong Answer

Solution code:
# Range Mininum Query
# 平方分割
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
import math
import functools as ft
MAX = int(math.pow(2,31)-1)

par = [int(item) for item in input().split()]
span = math.floor(math.sqrt(par[0]))
data = [MAX for i in range(par[0])]
backet = [MAX for i in range(math.ceil(par[0]/span))]

def dump_data():
    print(" === DEBUG === ")
    print("DATA:\t" + ft.reduce(lambda x, y: x + str(y) + " ", data, "") )
    print("BACKET:\t" + ft.reduce(lambda x, y: x + str(y) + " ", backet, "") )

def update(i, x):
    data[i] = x
    result = MAX
    buf = int(i/span)
    for i in range(span):
        if buf * span + i >= par[0]:
            break
        if data[buf * span + i] < result:
            result = data[buf * span + i]
    backet[buf] = result


# 0 1 2 3 4 5 6 7 8 9

def minimum(x, y):
    b_min = math.ceil(x/span)
    b_max = math.ceil(y/span)
    print("x: " + str(x) + " y: "+str(y))
    print("backet from: " + str(b_min) + " to:" +str(b_max))
    result = MAX

    for i in range(x, min(y+1, b_min * span)):
        if data[i] < result:
             result = data[i]
    for i in range(b_min, b_max):
        if backet[i] < result:
             result = backet[i]
    for i in range(max(x, b_max * span), y+1):
        if data[i] < result:
             result = data[i]

    return result


for i in range(par[1]):
    line = [int(item) for item in input().split()]
    #print(line)
    dump_data()
    if line[0] == 0:
        update(line[1], line[2])
    else:
        print(minimum(line[1], line[2]))

Submission status: Wrong Answer

Solution code:
# Range Mininum Query
# 平方分割
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
import math
import functools as ft
MAX = int(math.pow(2,31)-1)

par = [int(item) for item in input().split()]
span = math.floor(math.sqrt(par[0]))
data = [MAX for i in range(par[0])]
backet = [MAX for i in range(math.ceil(par[0]/span))]

def dump_data():
    print(" === DEBUG === ")
    print("DATA:\t" + ft.reduce(lambda x, y: x + str(y) + " ", data, "") )
    print("BACKET:\t" + ft.reduce(lambda x, y: x + str(y) + " ", backet, "") )

def update(i, x):
    data[i] = x
    result = MAX
    buf = int(i/span)
    for i in range(span):
        if buf * span + i >= par[0]:
            break
        if data[buf * span + i] < result:
            result = data[buf * span + i]
    backet[buf] = result


# 0 1 2 3 4 5 6 7 8 9

def minimum(x, y):
    b_min = math.ceil(x/span)
    b_max = math.ceil(y/span)
    #print("x: " + str(x) + " y: "+str(y))
    #print("backet from: " + str(b_min) + " to:" +str(b_max))
    result = MAX

    for i in range(x, min(y+1, b_min * span)):
        if data[i] < result:
             result = data[i]
    for i in range(b_min, b_max):
        if backet[i] < result:
             result = backet[i]
    for i in range(max(x, b_max * span), y+1):
        if data[i] < result:
             result = data[i]

    return result


for i in range(par[1]):
    line = [int(item) for item in input().split()]
    #print(line)
    #dump_data()
    if line[0] == 0:
        update(line[1], line[2])
    else:
        print(minimum(line[1], line[2]))

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)


def initRMQ(n, D):
    n_ = 1

    while n_ < n:
        n_ *= 2

    for i in range(2*n_ - 1):
        D.append(2147483647)

    return n_


def update(k, a):
    k += n_ - 1
    D[k] = a
    while k > 0:
        k = int((k - 1) / 2)
        D[k] = min(D[k*2 + 1], D[k*2 + 2])


def findMin(a, b):
    return query(a, b + 1, 0, 0, n)


def query(a, b, k, l, r):
    #print('q', a, b, k, l, r)
    if r <= a or b <= l:
        return 2147483647

    if a <= l and r <= b:
        return D[k]

    vl = query(a, b, k*2 + 1, l, int((l + r)/2))
    vr = query(a, b, k*2 + 2, int((l + r)/2), r)

    return min(vl, vr)


if __name__ == '__main__':
    n, q = map(int, input().split())

    D = []
    n_ = initRMQ(n, D)

    for _ in range(q):
        #print(D)
        c, x, y = map(int, input().split())

        if c == 0:
            update(x, y)

        else :
            print(findMin(x, y))

Submission status: Wrong Answer

Solution code:
import math

INIT_VAL = pow(2, 31)-1

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.height = math.ceil(math.log2(n))
        self.nodes = [INIT_VAL for i in range(pow(2, self.height+1)-1)]
        self.leaf_start = pow(2, self.height)-1

    def update(self, i, x):
        pntr = self.leaf_start + i
        self.nodes[pntr] = x
        while True:
            pntr = (pntr-1)//2
            if self.nodes[pntr] > x:
                self.nodes[pntr] = x
            else:
                break
            if pntr == 0: break

    def __query(self, s, t, k, l, r):
        if t - s <= 0: return INIT_VAL
        if r <= s or t <= l: return INIT_VAL
        if l == s and t == r: return self.nodes[k]
        else:
            m = (l+r)//2
            vl = self.__query(s, m, k*2+1, l, m)
            vr = self.__query(m, t, k*2+2, m, r)
            return min(vl, vr)

    def find(self, s, t):
        return self.__query(s, t+1, 0, 0, pow(2, self.height))

n, q = list(map(int, input().split(' ')))
st = SegmentTree(n)
for i in range(q):
    com, x, y = list(map(int, input().split(' ')))
    if com == 0:
        st.update(x, y)
    elif com == 1:
        print(st.find(x, y))

Submission status: Wrong Answer

Solution code:
import math

INIT_VAL = pow(2, 31)-1

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.height = math.ceil(math.log2(n))
        self.nodes = [INIT_VAL for i in range(pow(2, self.height+1)-1)]
        self.leaf_start = pow(2, self.height)-1

    def update(self, i, x):
        pntr = self.leaf_start + i
        self.nodes[pntr] = x
        while True:
            pntr = (pntr-1)//2
            if pntr == -1: break
            l, r = pntr*2 + 1, pntr*2 + 2
            self.nodes[pntr] = min(self.nodes[l], self.nodes[r])

    def __query(self, s, t, k, l, r):
        if t - s <= 0: return INIT_VAL
        if r <= s or t <= l: return INIT_VAL
        if l == s and t == r: return self.nodes[k]
        else:
            m = (l+r)//2
            vl = self.__query(s, m, k*2+1, l, m)
            vr = self.__query(m, t, k*2+2, m, r)
            return min(vl, vr)

    def find(self, s, t):
        return self.__query(s, t+1, 0, 0, pow(2, self.height))

n, q = list(map(int, input().split(' ')))
st = SegmentTree(n)
for i in range(q):
    com, x, y = list(map(int, input().split(' ')))
    if com == 0:
        st.update(x, y)
    elif com == 1:
        print(st.find(x, y))

Submission status: Wrong Answer

Solution code:
import math

INIT_VAL = pow(2, 31)-1

class SegmentTree():
    def __init__(self, n):
        self.n = n
        self.height = math.ceil(math.log2(n))
        self.nodes = [INIT_VAL for i in range(pow(2, self.height+1)-1)]
        self.leaf_start = pow(2, self.height)-1

    def update(self, i, x):
        pntr = self.leaf_start + i
        self.nodes[pntr] = x
        while True:
            pntr = (pntr-1)//2
            if pntr == -1: break
            l, r = pntr*2 + 1, pntr*2 + 2
            self.nodes[pntr] = min(self.nodes[l], self.nodes[r])
            if self.nodes[pntr] != x: break

    def __query(self, s, t, k, l, r):
        if t - s <= 0: return INIT_VAL
        if r <= s or t <= l: return INIT_VAL
        if l == s and t == r: return self.nodes[k]
        else:
            m = (l+r)//2
            if t <= m:
                return self.__query(s, t, k*2+1, l, m)
            elif m <= s:
                return self.__query(s, t, k*2+2, m, r)
            else:
                vl = self.__query(s, m, k*2+1, l, m)
                vr = self.__query(m, t, k*2+2, m, r)
                return min(vl, vr)

    def find(self, s, t):
        return self.__query(s, t+1, 0, 0, pow(2, self.height))

n, q = list(map(int, input().split(' ')))
st = SegmentTree(n)
for i in range(q):
    com, x, y = list(map(int, input().split(' ')))
    if com == 0:
        st.update(x, y)
    elif com == 1:
        print(st.find(x, y))

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import heapq
import itertools
import operator
import sys


def main():
    int_max = 2 ** 31 - 1
    n, q = map(int, sys.stdin.readline().split())
    dat = [int_max] * (131072 * 2 - 1)

    def update(i, x):
        i += n - 1
        dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return int_max
        if a <= l and r <= b:
            return dat[k]
        else:
            vl = query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = query(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)

    for _ in range(q):
        com, x, y = map(int, sys.stdin.readline().split())
        if com == 0:
            update(x, y)
        elif com == 1:
            print(query(x, y, 0, 0, n))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import heapq
import itertools
import operator
import sys


def main():
    int_max = 2 ** 31 - 1
    n, q = map(int, sys.stdin.readline().split())
    dat = [int_max] * (131072 * 2 - 1)

    def update(i, x):
        i += n - 1
        dat[i] = x
        while i > 0:
            i = (i - 1) // 2
            dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return int_max
        if a <= l and r <= b:
            return dat[k]
        else:
            vl = query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = query(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)

    for _ in range(q):
        com, x, y = map(int, sys.stdin.readline().split())
        if com == 0:
            update(x, y)
        elif com == 1:
            print(query(x, y + 1, 0, 0, n))


if __name__ == "__main__":
    main()