結果

問題 No.1031 いたずら好きなお姉ちゃん
ユーザー lam6er
提出日時 2025-03-31 17:57:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,396 bytes
コンパイル時間 300 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 112,344 KB
最終ジャッジ日時 2025-03-31 17:58:42
合計ジャッジ時間 10,150 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    p = list(map(int, input[1:n+1]))
    p = [x - 1 for x in p]  # Convert to 0-based
    
    # Helper function to compute previous and next smaller/larger elements
    def get_prev_next_smaller(arr):
        stack = []
        n = len(arr)
        prev_smaller = [-1] * n
        next_smaller = [n] * n
        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                top = stack.pop()
                next_smaller[top] = i
            if stack:
                prev_smaller[i] = stack[-1]
            stack.append(i)
        return prev_smaller, next_smaller
    
    def get_prev_next_larger(arr):
        stack = []
        n = len(arr)
        prev_larger = [-1] * n
        next_larger = [n] * n
        for i in range(n):
            while stack and arr[stack[-1]] < arr[i]:
                top = stack.pop()
                next_larger[top] = i
            if stack:
                prev_larger[i] = stack[-1]
            stack.append(i)
        return prev_larger, next_larger
    
    # Compute for smaller and larger elements
    prev_sm, next_sm = get_prev_next_smaller(p)
    prev_lg, next_lg = get_prev_next_larger(p)
    
    # Function to count pairs for condition A: i < j, p[i] > p[j], and in [i..j], p[i] is max, p[j] is min
    def count_condition_A():
        res = 0
        for j in range(n):
            # p[j] is min, find i's where i is in [prev_sm[j]+1 ... j-1], and next_lg[i] >=j
            left = prev_sm[j] + 1
            if left > j:
                continue
            for i in range(left, j):
                if next_lg[i] >= j:
                    res += 1
        return res
    
    # Function to count pairs for condition B: i < j, p[i] < p[j], and in [i..j], p[i] is min, p[j] is max
    def count_condition_B():
        res = 0
        for j in range(n):
            # p[j] is max, find i's where i is in [prev_lg[j]+1 ... j-1], and next_sm[i] >=j
            left = prev_lg[j] + 1
            if left > j:
                continue
            for i in range(left, j):
                if next_sm[i] >= j:
                    res += 1
        return res
    
    # The total number of valid pairs is the sum of both conditions
    total = count_condition_A() + count_condition_B()
    print(total)

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