結果

問題 No.1031 いたずら好きなお姉ちゃん
コンテスト
ユーザー lam6er
提出日時 2025-04-16 00:04:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,926 ms / 3,500 ms
コード長 4,208 bytes
コンパイル時間 538 ms
コンパイル使用メモリ 81,408 KB
実行使用メモリ 112,780 KB
最終ジャッジ日時 2025-04-16 00:06:21
合計ジャッジ時間 29,535 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    p = list(map(int, input[1:n+1]))
    
    def compute_L_max(p):
        n = len(p)
        L_max = [-1] * n
        stack = []
        for j in range(n):
            while stack and p[stack[-1]] <= p[j]:
                stack.pop()
            if stack:
                L_max[j] = stack[-1]
            else:
                L_max[j] = -1
            stack.append(j)
        return L_max
    
    def compute_R_min(p):
        n = len(p)
        R_min = [n] * n
        stack = []
        for i in range(n-1, -1, -1):
            while stack and p[stack[-1]] >= p[i]:
                stack.pop()
            if stack:
                R_min[i] = stack[-1]
            else:
                R_min[i] = n
            stack.append(i)
        return R_min
    
    def compute_L_min(p):
        n = len(p)
        L_min = [-1] * n
        stack = []
        for j in range(n):
            while stack and p[stack[-1]] >= p[j]:
                stack.pop()
            if stack:
                L_min[j] = stack[-1]
            else:
                L_min[j] = -1
            stack.append(j)
        return L_min
    
    def compute_R_max(p):
        n = len(p)
        R_max = [n] * n
        stack = []
        for i in range(n-1, -1, -1):
            while stack and p[stack[-1]] <= p[i]:
                stack.pop()
            if stack:
                R_max[i] = stack[-1]
            else:
                R_max[i] = n
            stack.append(i)
        return R_max
    
    L_max = compute_L_max(p)
    R_min = compute_R_min(p)
    L_min = compute_L_min(p)
    R_max = compute_R_max(p)
    
    class Block:
        def __init__(self, data):
            self.data = data
            self.sorted_data = sorted(data)
        def count_gt(self, x):
            return len(self.sorted_data) - bisect.bisect_right(self.sorted_data, x)
    
    class BlockArray:
        def __init__(self, arr, block_size):
            self.block_size = block_size
            self.blocks = []
            self.n = len(arr)
            for i in range(0, self.n, block_size):
                block_data = arr[i:i+block_size]
                self.blocks.append(Block(block_data))
        def query_range(self, l, r, x):
            if l > r:
                return 0
            count = 0
            block_size = self.block_size
            start_block = l // block_size
            end_block = r // block_size
            if start_block == end_block:
                block = self.blocks[start_block]
                start_in_block = l % block_size
                end_in_block = r % block_size
                for i in range(start_in_block, end_in_block + 1):
                    if block.data[i] > x:
                        count += 1
            else:
                block_start = self.blocks[start_block]
                start_in_block = l % block_size
                for i in range(start_in_block, len(block_start.data)):
                    if block_start.data[i] > x:
                        count += 1
                for b in range(start_block + 1, end_block):
                    count += self.blocks[b].count_gt(x)
                block_end = self.blocks[end_block]
                end_in_block = r % block_size
                for i in range(0, end_in_block + 1):
                    if block_end.data[i] > x:
                        count += 1
            return count
    
    block_size = int(n**0.5) + 1
    block_R_min = BlockArray(R_min, block_size)
    block_R_max = BlockArray(R_max, block_size)
    
    ans = 0
    for j in range(n):
        left_case1 = L_max[j] + 1
        right_case1 = j - 1
        contribution_case1 = 0
        if left_case1 <= right_case1:
            contribution_case1 = block_R_min.query_range(left_case1, right_case1, j)
        
        left_case2 = L_min[j] + 1
        right_case2 = j - 1
        contribution_case2 = 0
        if left_case2 <= right_case2:
            contribution_case2 = block_R_max.query_range(left_case2, right_case2, j)
        
        ans += contribution_case1 + contribution_case2
    
    print(ans)

if __name__ == "__main__":
    main()
0