結果

問題 No.1031 いたずら好きなお姉ちゃん
コンテスト
ユーザー 已经死了
提出日時 2025-08-17 20:53:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 382 ms / 3,500 ms
コード長 2,255 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,968 KB
実行使用メモリ 127,992 KB
最終ジャッジ日時 2025-08-17 20:53:34
合計ジャッジ時間 20,444 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import os,sys,random,threading
from random import randint,choice,shuffle
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
from bisect import bisect_left,bisect_right
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
from heapq import  heapify,heappop,heappush
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
from decimal import Decimal,getcontext
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7)
inf = 1<<60
py = lambda :print("YES")
pn = lambda :print("NO")




class BIT1:
    """单点修改,区间和查询"""

    __slots__ = "size", "bit", "tree"

    def __init__(self, n: int):
        self.size = n
        self.bit = n.bit_length()
        self.tree = [0]*(n+1)

    def add(self, index: int, delta: int) -> None:
        # index 必须大于0
        while index <= self.size:
            self.tree[index]+=delta
            index += index & -index

    def _query(self, index: int) -> int: 
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= index & -index
        return res

    def query(self, left: int, right: int) -> int:
        return self._query(right) - self._query(left - 1)


def check(arr):
    res=0
    mx=[[-1,inf]] 
    mn=[]
    bit=BIT1(n+10)
    for i in range(n):
        while mx[-1][1]<=arr[i]:
            mx.pop()
        while mn and mn[-1][1]>arr[i]:
            j,_=mn.pop()
            bit.add(j+1,-1)
        res+=bit.query(mx[-1][0]+2,i+1)
        bit.add(i+1,1)
        mx.append([i,arr[i]])
        mn.append([i,arr[i]])
    return res


t=1
for _ in range(t):
    n=ii()
    arr=li()
    res=2*n+check(arr)+check(arr[::-1])
    stk=[]
    for a in arr:
        if stk and stk[-1][0]==a:
            stk[-1][1]+=1
        else:
            stk.append([a,1])
    for a,c in stk:
        res-=(1+c)*c//2
    print(res-n)
0