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)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
3420 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
3420 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
3420 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
