oj.uz

답안 #884526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
884526 2023-12-07T15:21:16 Z tsumondai Simple game (IZhO17_game) Python 3
0 / 100
 13 ms 3420 KB 
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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 3420 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 3420 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 3420 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -