C - 部分文字列と括弧

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500

問題文

() からなる文字列 S が与えられます。次の条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組はいくつあるでしょうか。

条件: - Si 文字目から j 文字目まで (両端を含む) を取り出した時、その文字列は括弧の対応が取れている

括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。

  • 空文字列
  • ある括弧の対応が取れている文字列 A, B が存在し、 A, B をこの順に連結した文字列
  • ある括弧の対応が取れている文字列 A が存在し、 (, A, ) をこの順に連結した文字列

制約

  • 1 ≤ |S| ≤ 10^5
  • S(, ) のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

S

出力

条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組の個数を出力せよ。


入力例 1

((())

出力例 1

2
  • S2 文字目から 5 文字目までを取り出すと、 (()) です。これは括弧の対応が取れています。
  • S3 文字目から 4 文字目までを取り出すと、 () です。これは括弧の対応が取れています。

よって、 (2, 5) および (3, 4) が条件を満たします。


入力例 2

(()()(())(

出力例 2

7