https://codeforces.com/contest/1556/problem/C
1秒、256 MBメモリ
input :

t (1 ≤ t ≤ 1000)

c1, c2, …, cn (1 ≤ ci ≤ 109)

output :

Output a single integer — the total number of subsegments of the original bracket sequence, which are regular bracket sequences.
正しいかっこを生成できる個数を出力してください.

条件:

かっこをそのまま表示すると、大きすぎるので数字で入力します.単数索引は「(」の個数を表し、偶数索引は「)」の個数を表す.

連続部分配列で作成できるすべての正しいかっこ数を計算します.

時間がかかりすぎた.実は今はまだ難しい
まず、前から後ろにカッコをすべて作成することを考慮します.移動には時間がかかるだけでなく、漏れが多く発生します.
現在を基準に、以前に作成したカッコをチェックすると便利です.
まずかっこを確認するときはペアで確認します
これにより、このときに作成できる正しいかっこの個数を決定できます.この場合、2つのケースがあります.
かっこが

個以上残っている場合は、->右かっこの数が正しいかっこになります.

の括弧が前の左括弧と一致する場合->現在の残りの左括弧+右括弧-最初の括弧が閉じたときの残りの左括弧数

スタック初期化

スタックを最初に作成するときは、[0,0]を格納します.これまでカッコがなかったためです.
[0]前の左かっこの個数
[1]の2番目のオプションは、このカッコを付けて正しい式を生成できる数を格納します.
では、文の回転を繰り返すと、残りの左かっこの数はopne-clossの数で計算できます.
この時は負数でも放っておく負数については,閉じた後に新たな括弧を付けることはできないと考えられる.
すなわち,新しい括弧が必要であり,[cur open,0]が追加される.

前のかっこを現在の条件で貼り付けます

これで、以前に存在したカッコが決定されると、前の[0]はcur openより大きい.
右括弧が増えたからといって、それを埋め尽くしたのです.
したがって、このカッコで増加した値を正解に追加します.
同じ値なら?
追加を続行できますOpen、closeが同じで、後ろのカッコも同じであれば、この2つを追加することで2つの正しいカッコを作成することができますので、この場合も考慮してください.

新しいかっこ

以前に存在したカッコにカッコを付けることはできません->スタックが空です.新規作成
上記でない場合は[cur open,1]を追加します.現在開いているかっこの数を記録し、比較します.
上から右かっこで数える.これから.
現在のかっこを作成するときは、前に保持したかっこが含まれていることを確認します.
次に、他のコンテンツを検索するときにスタックをループして、カッコ自体を追加できるかどうかを確認できます.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

ans, cur_open = 0, 0
s = [[0, 0]]

for i in range(0, n, 2):
    if i + 1 >= n:
        continue

    open_bracket = data[i]
    close_bracket = data[i + 1]

    cur_open += open_bracket - close_bracket
    ans += min(close_bracket, cur_open + close_bracket - s[0][0])
    while s and s[-1][0] > cur_open:
        ans += s[-1][1]
        s.pop()

    if s and s[-1][0] == cur_open:
        ans += s[-1][1]
        s[-1][1] += 1
    else:
        if s:
            s.append([cur_open, 1])
        else:
            s.append([cur_open, 0])

print(ans)