結果

問題 No.1031 いたずら好きなお姉ちゃん
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:48:38
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,503 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 82,788 KB
実行使用メモリ 122,664 KB
最終ジャッジ日時 2025-03-20 20:48:54
合計ジャッジ時間 10,730 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    sys.setrecursionlimit(1 << 25)
    n, *rest = map(int, sys.stdin.read().split())
    p = rest[:n]

    logn = max(1, math.floor(math.log2(n))) if n else 0
    st_min = []
    st_max = []

    # Build sparse tables for RMQ and Range Max
    st_min = [[0] * n for _ in range(logn + 1)]
    st_max = [[0] * n for _ in range(logn + 1)]

    for i in range(n):
        st_min[0][i] = p[i]
        st_max[0][i] = p[i]

    for k in range(1, logn + 1):
        for i in range(n - (1 << k) + 1):
            st_min[k][i] = min(st_min[k-1][i], st_min[k-1][i + (1 << (k-1))])
            st_max[k][i] = max(st_max[k-1][i], st_max[k-1][i + (1 << (k-1))])

    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i//2] + 1

    def get_min(l, r):
        length = r - l + 1
        k = log_table[length]
        return min(st_min[k][l], st_min[k][r - (1 << k) + 1])

    def get_max(l, r):
        length = r - l + 1
        k = log_table[length]
        return max(st_max[k][l], st_max[k][r - (1 << k) + 1])

    seen = set()
    for i in range(n):
        for j in range(i+1, n):
            a = min(p[i], p[j])
            b = max(p[i], p[j])
            current_min = get_min(i, j)
            current_max = get_max(i, j)
            if current_min == a and current_max == b:
                if (i, j) not in seen and (j, i) not in seen:
                    seen.add((i, j))
    print(len(seen))

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