Rectangle Concatenation

AtCoder

IDarc179_e

Time2000ms

Memory256MB

Difficulty—

For positive integers $h$ and $w$, let $(h,w)$ denote a rectangle with height $h$ and width $w$. In this problem, we do not consider rotating the rectangles, and the rectangles $(h,w)$ and $(w,h)$ are distinguished when $h \neq w$. A sequence of rectangles $((h_1,w_1),(h_2,w_2),\dots ,(h_n,w_n))$ is called a **rectangle generation sequence** if there exists a method that successfully follows the steps below: * Let the rectangle $X$ be $(h_1,w_1)$. Hereafter, let $H$ and $W$ respectively denote the height and width of the rectangle $X$ at each step. * For $i=2,3,\dots ,n$, perform one of the following operations. If neither can be performed, the procedure unsuccessfully terminates. * If the height of $X$ is equal to $h_i$, attach the rectangle $(h_i,w_i)$ horizontally to $X$. Formally, if $H=h_i$ at that time, replace $X$ with the rectangle $(H,W+w_i)$. * If the width of $X$ is equal to $w_i$, attach the rectangle $(h_i,w_i)$ vertically to $X$. Formally, if $W=w_i$ at that time, replace $X$ with the rectangle $(H+h_i,W)$. * If the above series of operations does not fail, the procedure successfully terminates. * * * You are given $N$ rectangles. The $i$\-th rectangle has a height of $H_i$ and a width of $W_i$. Find the number of pairs of positive integers $(l,r)$ that satisfy $1 \le l \le r \le N$ and the following condition: * The sequence of rectangles $((H_l,W_l),(H_{l+1},W_{l+1}),\dots ,(H_r,W_r))$ is a rectangle generation sequence. ## Constraints * $1 \leq N \leq 3 \times 10^5$ * $1 \leq H_i, W_i \leq 10^6$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $H_1$ $W_1$ $H_2$ $W_2$ $\vdots$ $H_N$ $W_N$ [samples]

Samples

Input #1

Output #1

7

The pairs $(l,r)$ that satisfy the condition are $(1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(4,4)$; there are seven.
For example, for $(l,r)=(2,4)$, the procedure succeeds if the first attachment is done vertically and the second is done horizontally.

Input #2

Output #2

Input #3

1
1000000 1000000

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Rectangle Concatenation",
    "description": {
      "content": "For positive integers $h$ and $w$, let $(h,w)$ denote a rectangle with height $h$ and width $w$. In this problem, we do not consider rotating the rectangles, and the rectangles $(h,w)$ and $(w,h)$ are",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc179_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For positive integers $h$ and $w$, let $(h,w)$ denote a rectangle with height $h$ and width $w$. In this problem, we do not consider rotating the rectangles, and the rectangles $(h,w)$ and $(w,h)$ are...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments