No.1965 Heavier
タグ : / 解いたユーザー数 96
作問者 :
milkcoffee
/ テスター :
platinum
Problem Statement
There are $N$ people numbered from $1$ to $N$, and pieces of luggage also numbered from $1$ to $N$.
The body weight of person $i$ is $A_i$, and the weight of luggage $i$ is $B_i$.
The body weights of the $N$ people are all distinct, and the people are numbered in increasing order of body weight. That is, $A_i < A_{i+1} \ (1 \leq i \leq N-1)$ holds.
A match between person $i$ and person $j$ $(i < j)$ is defined as follows.
- Person $i$ holds luggage $i$ and person $j$ holds luggage $j$.
- If $B_i < B_j$, they exchange the luggage they are holding. In other words, the person with the lighter body weight ends up holding the heavier luggage.
- The person whose sum of their own body weight and the weight of the luggage they are currently holding is strictly larger wins. If the sums are equal, the match is a draw.
For $(1 \leq L < R \leq N)$, when the interval $[L,R]$ satisfies the following, $[L,R]$ is called a good interval.
- For every pair $(i,j) \ (L \leq i < j \leq R)$ in the interval, person $j$ beats person $i$. That is, in every pair, the person with the heavier body weight wins.
Find the number of good intervals.
Input
$N$ $A_1 \ A_2 \ \dots A_N$ $B_1 \ B_2 \ \dots B_N$
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_1 < A_2 < \dots < A_N \leq 10^9$
- $1 \leq B_i \leq 10^9 \ (1 \leq i \leq N)$
- All input values are integers.
Output
Print the number of good intervals.
Sample
Sample 1
Input
3 2 4 8 2 1 2
Output
3
In the match between person $1$ and person $2$, they do not exchange luggage. Since $A_1+B_1 < A_2+B_2$, person $2$ wins.
In the match between person $1$ and person $3$, they do not exchange luggage. Since $A_1+B_1 < A_3+B_3$, person $3$ wins.
In the match between person $2$ and person $3$, they exchange luggage. Since $A_2+B_3 < A_3+B_2$, person $3$ wins.
Since person $2$ beats person $1$, the interval $[1,2]$ is a good interval.
Since person $3$ beats person $2$, the interval $[2,3]$ is a good interval.
Since person $2$ beats person $1$, and person $3$ beats person $1$ and person $2$, the interval $[1,3]$ is a good interval.
Sample 2
Input
2 1 10 1 1000
Output
0
Since person $2$ does not beat person $1$, the interval $[1,2]$ is not a good interval.
Sample 3
Input
2 1 2 2 3
Output
0
Person $1$ and person $2$ draw.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。