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_rec(self, v, tl, tr, l, r, x): """ Segment tree min. Cherche le plus petit i dans [l,r] tq a[i] <= x """ if tl > r or tr < l: return -1 if self.Tree[v] > x: return -1 if tl == tr: return tl tm = (tl + tr) // 2 left = self.first_smaller_than_rec(2*v, tl, tm, l, r, x) if left != -1: return left return self.first_smaller_than_rec(2*v+1, tm+1, tr, l, r, x) # 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 40%)

=======