제출 #1314287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314287		ra2iss	Deda (COCI17_deda)	Pypy 3	20 / 140	398 ms	59196 KiB

deda

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

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'deda.py'...

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

=======

• Subtask 1: 20 / 140