Submission #884526

#	Time	Username	Problem	Language	Result	Execution time	Memory
884526		tsumondai	Simple game (IZhO17_game)	Cpython 3	0 / 100	13 ms	3420 KiB

game

from collections import defaultdict

def solve(n, m, y, operations):
  """
  Solves the competitive programming problem.

  Args:
    n: Number of vertices.
    m: Number of operations.
    y: List of initial vertex heights.
    operations: List of operations.

  Returns:
    List of intersection counts for each query.
  """

  # Initialize a sweep line and a dictionary for tracking active segments.
  sweep_line = []
  active_segments = defaultdict(list)

  # Process each operation.
  intersections = []
  for op in operations:
    if op[0] == 1:
      # Update vertex height.
      pos, val = op[1], op[2]
      y[pos - 1] = val

      # Remove old segment from sweep line and active segments.
      old_segment = (pos - 1, y[pos - 2], y[pos - 1])
      active_segments[old_segment[1]].remove(old_segment)
      sweep_line.remove(old_segment)

      # Add new segment to sweep line and active segments.
      if pos > 1:
        new_segment = (pos - 2, y[pos - 3], y[pos - 2])
        active_segments[new_segment[1]].append(new_segment)
        sweep_line.append(new_segment)

    else:
      # Count intersections for horizontal line.
      height = op[1]
      count = 0

      # Sweep line from bottom to top.
      while sweep_line:
        top, bottom, _ = sweep_line[0]
        if bottom > height:
          break

        # Check if line intersects active segment.
        if bottom <= height <= top:
          count += 1

        # Remove segment from active segments if its top end is reached.
        if top == height:
          active_segments[bottom].remove((bottom, bottom, top))
          sweep_line.pop(0)

      intersections.append(count)

  return intersections

# Read input.
n, m = map(int, input().split())
y = list(map(int, input().split()))
operations = []
for _ in range(m):
  operations.append(list(map(int, input().split())))

# Solve the problem and print output.
intersections = solve(n, m, y, operations)
for i in intersections:
  print(i)

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51