Submission #1161504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161504		6530089	Swap Swap Sort (CCO21_day1problem1)	Pypy 3	0 / 25	5096 ms	200176 KiB

Main

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index, value):
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def sum(self, index):
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

    def range_sum(self, left, right):
        return self.sum(right) - self.sum(left - 1)

def count_inversions(arr, K):
    # Map values to their positions in P
    ft = FenwickTree(K)
    inv_count = 0
    for i in range(len(arr)):
        inv_count += ft.range_sum(arr[i] + 1, K)
        ft.add(arr[i], 1)
    return inv_count

def swap_and_update(swaps, pos_map, A, K):
    inv_count = count_inversions([pos_map[x] for x in A], K)
    result = []
    
    for j in swaps:
        val1, val2 = pos_map[j], pos_map[j + 1]
        
        # Swap in position map
        pos_map[j], pos_map[j + 1] = val2, val1
        
        # Adjust inversion count
        affected_indices = [x for x in A if x in {j, j + 1}]
        new_inversions = count_inversions([pos_map[x] for x in affected_indices], K)
        inv_count = new_inversions  # Update with new inversions count
        
        result.append(inv_count)

    return result

# Reading input
import sys
input = sys.stdin.read
data = input().split()
idx = 0

# Read N, K, Q
N, K, Q = map(int, data[idx:idx+3])
idx += 3

# Read array A
A = list(map(int, data[idx:idx+N]))
idx += N

# Read swap queries
swaps = list(map(int, data[idx:idx+Q]))

# Initial target permutation
pos_map = {i: i - 1 for i in range(1, K + 1)}

# Process swaps and print results
results = swap_and_update(swaps, pos_map, A, K)
sys.stdout.write("\n".join(map(str, results)) + "\n")

Compilation message (stdout)

Compiling 'Main.py'...

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

=======

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 5
• Subtask 4: 0 / 14