import sys input = sys.stdin.readline INF = 10**18 class SegmentTree: def __init__(self, L): N = 1 n = len(L) while N < n: N *= 2 Tree = [INF]*(2*N) for i in range(n): Tree[N + i] = L[i] for i in range(N - 1, 0, -1): Tree[i] = min(Tree[2*i], Tree[2*i+1]) self.N = N self.Tree = Tree def point_update(self, i, x): idx = self.N + i self.Tree[idx] = x idx //= 2 while idx >= 1: self.Tree[idx] = min(self.Tree[2*idx], self.Tree[2*idx+1]) idx //= 2 def first_smaller_than(self, l, r, x): N = self.N T = self.Tree l += N r += N candidates = [] while l <= r: if l % 2 == 1: if T[l] <= x: candidates.append(l) l += 1 if r % 2 == 0: if T[r] <= x: candidates.append(r) r -= 1 l //= 2 r //= 2 if not candidates: return -1 v = min(candidates) while v < N: if T[2*v] <= x: v = 2*v else: v = 2*v+1 return v - N # Lecture des entrées N, Q = map(int, input().split()) stops = [INF]*N seg = SegmentTree(stops) for _ in range(Q): line = input().split() if line[0] == 'M': X = int(line[1]) A = int(line[2]) seg.point_update(A-1, X) else: # 'D' Y = int(line[1]) B = int(line[2]) res = seg.first_smaller_than(B-1, N-1, Y) if res == -1: print(-1) else: print(res+1) # convertir en 1-based

Compiling 'deda.py'...

=======
  adding: __main__.pyc (deflated 42%)

=======