Submission #1148827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148827		andrejikus	방벽 (JOI15_walls)	Pypy 3	0 / 100	135 ms	48796 KiB

walls

import bisect

def min_barrier_moves(N, M, barriers, attacks):
    # Sort barriers by Ai
    barriers.sort()
    attack_positions = sorted(attacks)
    
    # Extract Ai and Bi separately for binary search
    A = [barriers[i][0] for i in range(N)]
    B = [barriers[i][1] for i in range(N)]
    
    # Movement count per barrier
    moves = [0] * N

    for P in attack_positions:
        # Find the nearest barrier that can cover attack P
        idx = bisect.bisect_left(B, P)  # First barrier where Bi >= P
        
        if idx < N and A[idx] <= P <= B[idx]:
            # If P is already covered, no need to move
            continue

        # Otherwise, move the closest barrier
        left_idx = idx - 1 if idx > 0 else 0
        right_idx = idx if idx < N else N - 1
        
        if left_idx >= 0 and abs(A[left_idx] - P) < abs(A[right_idx] - P):
            # Move left barrier
            moves[left_idx] += abs(A[left_idx] - P)
            A[left_idx] = P
            B[left_idx] = P  # Adjust range to absorb attack
        else:
            # Move right barrier
            moves[right_idx] += abs(A[right_idx] - P)
            A[right_idx] = P
            B[right_idx] = P

    return moves

# Example usage
N = 4
M = 4
barriers = [(0, 3), (4, 4), (2, 7), (8, 11)]
attacks = [6, 4, 3, 8]

result = min_barrier_moves(N, M, barriers, attacks)
print("\n".join(map(str, result)))

Compilation message (stdout)

Compiling 'walls.py'...

=======
  adding: __main__.pyc (deflated 42%)

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 45
• Subtask 3: 0 / 45