API tools faq
paste
Advertisement
tensedtorch

Q2-trees

tensedtorch
May 18th, 2025
483
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.20 KB | None | 0 0
raw download clone embed print report
  1. import math
  2.  
  3. class SegmentTreeForPrevNext:
  4.     def __init__(self, n_elements: int):
  5.         self.n = n_elements
  6.         self.tree_leaf_start_idx = 1
  7.         while self.tree_leaf_start_idx < self.n:
  8.             self.tree_leaf_start_idx *= 2
  9.         self.tree = [0] * (2 * self.tree_leaf_start_idx)
  10.  
  11.     def mark_malicious(self, original_idx: int):
  12.         current_tree_node_idx = self.tree_leaf_start_idx + original_idx
  13.         if self.tree[current_tree_node_idx] == 1:
  14.             return
  15.         self.tree[current_tree_node_idx] = 1
  16.         while current_tree_node_idx > 1:
  17.             current_tree_node_idx //= 2
  18.             self.tree[current_tree_node_idx] = self.tree[current_tree_node_idx * 2] + self.tree[current_tree_node_idx * 2 + 1]
  19.  
  20.     def _find_rightmost_one_recursive(self, current_tree_node_idx: int,
  21.                                        node_L: int, node_R: int,
  22.                                        query_L: int, query_R: int) -> int:
  23.         if query_L > query_R or node_L > query_R or node_R < query_L or self.tree[current_tree_node_idx] == 0:
  24.             return -1
  25.         if node_L == node_R:
  26.             return node_L
  27.         mid = (node_L + node_R) // 2
  28.         res_right = self._find_rightmost_one_recursive(2 * current_tree_node_idx + 1, mid + 1, node_R, query_L, query_R)
  29.         if res_right != -1:
  30.             return res_right
  31.         res_left = self._find_rightmost_one_recursive(2 * current_tree_node_idx, node_L, mid, query_L, query_R)
  32.         return res_left
  33.  
  34.     def find_prev_malicious_site(self, original_idx: int) -> int:
  35.         if original_idx == 0:
  36.             return -1
  37.         return self._find_rightmost_one_recursive(1, 0, self.tree_leaf_start_idx - 1, 0, original_idx - 1)
  38.  
  39.     def _find_leftmost_one_recursive(self, current_tree_node_idx: int,
  40.                                       node_L: int, node_R: int,
  41.                                       query_L: int, query_R: int) -> int:
  42.         if query_L > query_R or node_L > query_R or node_R < query_L or self.tree[current_tree_node_idx] == 0:
  43.             return -1
  44.         if node_L == node_R:
  45.             return node_L
  46.         mid = (node_L + node_R) // 2
  47.         res_left = self._find_leftmost_one_recursive(2 * current_tree_node_idx, node_L, mid, query_L, query_R)
  48.         if res_left != -1:
  49.             return res_left
  50.         res_right = self._find_leftmost_one_recursive(2 * current_tree_node_idx + 1, mid + 1, node_R, query_L, query_R)
  51.         return res_right
  52.  
  53.     def find_next_malicious_site(self, original_idx: int) -> int:
  54.         if original_idx == self.n - 1:
  55.             return self.n
  56.         res = self._find_leftmost_one_recursive(1, 0, self.tree_leaf_start_idx - 1, original_idx + 1, self.n - 1)
  57.         return res if res != -1 else self.n
  58.  
  59. def findMinimumTime(password: str, attackOrder: list[int], m: int) -> int:
  60.     N = len(password)
  61.  
  62.     if N == 0:
  63.         return 0
  64.  
  65.     if m == 0:
  66.         return 1
  67.  
  68.     def count_substrings_from_length(k: int) -> int:
  69.         if k <= 0:
  70.             return 0
  71.         return k * (k + 1) // 2
  72.  
  73.     seg_tree = SegmentTreeForPrevNext(N)
  74.     current_total_clean_substrings = count_substrings_from_length(N)
  75.     total_possible_substrings = current_total_clean_substrings
  76.  
  77.     for t, attack_pos_1_indexed in enumerate(attackOrder):
  78.         time_step = t + 1
  79.         attack_idx_0_based = attack_pos_1_indexed - 1
  80.  
  81.         prev_mal_idx = seg_tree.find_prev_malicious_site(attack_idx_0_based)
  82.         next_mal_idx = seg_tree.find_next_malicious_site(attack_idx_0_based)
  83.  
  84.         len_old_segment = next_mal_idx - prev_mal_idx - 1
  85.         current_total_clean_substrings -= count_substrings_from_length(len_old_segment)
  86.  
  87.         len_left_segment = attack_idx_0_based - prev_mal_idx - 1
  88.         current_total_clean_substrings += count_substrings_from_length(len_left_segment)
  89.  
  90.         len_right_segment = next_mal_idx - attack_idx_0_based - 1
  91.         current_total_clean_substrings += count_substrings_from_length(len_right_segment)
  92.  
  93.         seg_tree.mark_malicious(attack_idx_0_based)
  94.  
  95.         num_malicious_substrings = total_possible_substrings - current_total_clean_substrings
  96.         if num_malicious_substrings >= m:
  97.             return time_step
  98.  
  99.     return -1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!