結果

問題 No.1439 Let's Compare!!!!
ユーザー lam6er
提出日時 2025-03-20 20:26:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 618 ms / 2,000 ms
コード長 2,715 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 147,716 KB
最終ジャッジ日時 2025-03-20 20:27:35
合計ジャッジ時間 6,884 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.size = 1
        while self.size < self.n:
            self.size <<= 1  # Find the next power of two
        self.min_tree = [float('inf')] * (2 * self.size)
        # Fill the leaves
        for i in range(self.n):
            self.min_tree[self.size + i] = data[i]
        # Build the tree upwards
        for i in range(self.size - 1, 0, -1):
            self.min_tree[i] = min(self.min_tree[2*i], self.min_tree[2*i+1])
    
    def update(self, pos, new_val):
        pos += self.size  # Translate to the leaf index
        self.min_tree[pos] = new_val
        # Move up to update the tree
        pos >>= 1
        while pos >= 1:
            new_min = min(self.min_tree[2*pos], self.min_tree[2*pos+1])
            if self.min_tree[pos] == new_min:
                break  # No change needed further up
            self.min_tree[pos] = new_min
            pos >>= 1
    
    def get_min(self):
        return self.min_tree[1]  # The root contains the min of the entire range

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    S = input[idx]; idx +=1
    T = input[idx]; idx +=1
    Q = int(input[idx]); idx +=1
    
    s_digits = list(S)
    t_digits = list(T)
    
    # Prepare initial data for the segment tree
    data = []
    for i in range(N):
        if s_digits[i] != t_digits[i]:
            data.append(i+1)  # Positions are 1-based in the problem
        else:
            data.append(float('inf'))
    
    tree = SegmentTree(data)
    
    for _ in range(Q):
        c_i = input[idx]; idx +=1
        x_i = int(input[idx]); idx +=1
        y_i = input[idx]; idx +=1
        
        # Adjust to 0-based index
        pos_in_digits = x_i -1
        if c_i == 'S':
            s_digits[pos_in_digits] = y_i
        else:
            t_digits[pos_in_digits] = y_i
        
        # Determine the new value for this position in the segment tree
        if s_digits[pos_in_digits] != t_digits[pos_in_digits]:
            new_val = x_i  # 1-based position
        else:
            new_val = float('inf')
        tree.update(pos_in_digits, new_val)
        
        # Query the minimal differing position
        min_pos = tree.get_min()
        if min_pos == float('inf'):
            print('=')
        else:
            # Compare the digits at min_pos (1-based)
            s_char = s_digits[min_pos -1]
            t_char = t_digits[min_pos -1]
            if s_char > t_char:
                print('>')
            elif s_char < t_char:
                print('<')
            else:
                print('=')

if __name__ == '__main__':
    main()
0