結果

問題 No.696 square1001 and Permutation 5
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:59:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,046 bytes
コンパイル時間 322 ms
コンパイル使用メモリ 81,760 KB
実行使用メモリ 269,468 KB
最終ジャッジ日時 2025-05-14 13:02:36
合計ジャッジ時間 22,816 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Fenwick tree (Binary Indexed Tree) implementation
class FenwickTree:
    """Fenwick Tree for prefix sums and point updates."""
    def __init__(self, size):
        """Initializes Fenwick Tree of given size."""
        # The tree structure uses 1-based indexing internally.
        # The array size needs to be 'size + 1' to accommodate index 'size'.
        self.tree = [0] * (size + 1)
        self.size = size

    def update(self, i, delta):
        """Adds delta to the element at index i."""
        # The index i must be 1 <= i <= self.size.
        # This method updates the value at index i and all necessary ancestors in the tree.
        while i <= self.size:
            self.tree[i] += delta
            # Move to the next index that represents a range covering index i.
            # This is done by adding the least significant bit (LSB).
            i += i & (-i) 

    def query(self, i):
        """Computes the prefix sum up to index i (sum of elements from 1 to i)."""
        # Handle query for index 0, which should logically return 0.
        if i <= 0:
             return 0
        # Ensure query index does not exceed the tree size.
        if i > self.size:
             i = self.size 

        s = 0
        # Sum values by traversing up the tree towards the root (index 0 conceptually).
        while i > 0:
            s += self.tree[i]
            # Move to the parent index in the implicit tree structure.
            # This is done by subtracting the least significant bit (LSB).
            i -= i & (-i) 
        return s

def solve():
    """Solves the permutation rank problem."""
    # Read the size of the permutation N from standard input.
    N = int(sys.stdin.readline())
    
    # Handle edge case N=0. Although problem states N>=1, being safe.
    if N == 0:
        print(1) # Define rank of empty permutation as 1? Standard is usually 1.
        return

    # Handle edge case N=1 explicitly.
    if N == 1:
         # Read the permutation line which contains '1'. We don't need the value.
         sys.stdin.readline() 
         # The only permutation (1) has rank 1.
         print(1) 
         return

    # Read the permutation p as a list of N integers.
    p = list(map(int, sys.stdin.readline().split()))

    # Calculate (N-1)! using Python's built-in arbitrary precision integers (BigInt).
    # This value is the factorial term needed for the first position (i=1).
    # Initialize factorial value to 1 (for 0!)
    current_factorial_val = 1
    # The loop calculates product of k=1 to N-1, which is (N-1)!
    for k in range(1, N): 
        current_factorial_val *= k
    
    # Initialize Fenwick tree of size N.
    # This tree will maintain the counts of available numbers.
    # Initially, all numbers from 1 to N are available.
    ft = FenwickTree(N)
    # Mark each number i from 1 to N as available by setting its count to 1.
    for i in range(1, N + 1):
        ft.update(i, 1) 

    # Initialize the total rank (0-based). Use BigInt to avoid overflow.
    total_rank = 0 
    
    # Iterate through the permutation positions from 1 to N.
    # The loop variable 'i' represents the current position index (1-based).
    for i in range(1, N + 1): 
        # Get the value p_i from the input list p. Since p is 0-indexed, use p[i-1].
        p_val = p[i-1]
        
        # Calculate k_{i-1}: the count of available numbers strictly less than p_val.
        # This is achieved by querying the Fenwick tree for the prefix sum up to p_val - 1.
        # The query ft.query(p_val - 1) sums counts of available numbers in {1, 2, ..., p_val - 1}.
        count_smaller_available = ft.query(p_val - 1)
        
        # The factorial term for position i is (N-i)!.
        # The variable `current_factorial_val` holds this value.
        
        # Add the contribution of this position to the total rank: k_{i-1} * (N-i)!
        term = count_smaller_available * current_factorial_val
        total_rank += term
        
        # Mark the number p_val as used (no longer available).
        # Update its count in Fenwick tree to 0 by applying an update of -1.
        ft.update(p_val, -1)
        
        # Update the factorial value for the next position (i+1).
        # The factorial needed for step i+1 is (N-(i+1))! = (N-i-1)!.
        # This is calculated by dividing the current factorial (N-i)! by (N-i).
        # This division is only valid if N-i > 0.
        if N - i > 0:
            # Use integer division // which works correctly for Python's BigInts.
            current_factorial_val //= (N - i)
        # If N - i == 0, it means we just processed the last element (i=N).
        # The factorial used was (N-N)! = 0! = 1. No further factorial update is needed.

    # The `total_rank` calculated represents the count of permutations lexicographically
    # smaller than p. This is the 0-based rank.
    # The problem asks for the 1-based rank, so add 1.
    print(total_rank + 1)

# Execute the main solution function when the script is run.
solve()
0