AtCoder Beginner Contest 247

E - Max Min

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $500$ points

### Problem Statement

We have a number sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$ and integers $X$ and $Y$. Find the number of pairs of integers $(L, R)$ satisfying all the conditions below.

• $1 \leq L \leq R \leq N$
• The maximum value of $A_L, A_{L+1}, \dots, A_R$ is $X$, and the minimum is $Y$.

### Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$
• $1 \leq Y \leq X \leq 2 \times 10^5$
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

$N$ $X$ $Y$
$A_1$ $A_2$ $\dots$ $A_N$

4 3 1
1 2 3 1

### Sample Output 1

4

$4$ pairs satisfy the conditions: $(L,R)=(1,3),(1,4),(2,4),(3,4)$.

5 2 1
1 3 2 4 1

### Sample Output 2

0

No pair $(L,R)$ satisfies the condition.

5 1 1
1 1 1 1 1

### Sample Output 3

15

It may hold that $X=Y$.

### Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

36

### 源码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
int N, X, Y;
int A[MAXN];

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> X >> Y;
for (int i = 0; i < N; i++)
cin >> A[i];
int i = 0;
long long ans = 0;
while (i < N)
{
vector<int> subseq;
while (i < N && A[i] >= Y && A[i] <= X)
{
subseq.push_back(A[i]);
i++;
}
if (!subseq.empty())
{
int l = 0, r = 0;
int cnt_X = 0, cnt_Y = 0;
if (subseq[0] == X)
cnt_X++;
if (subseq[0] == Y)
cnt_Y++;
while (l < subseq.size() && r < subseq.size())
{
if (!cnt_X || !cnt_Y)
{
r++;
if (subseq[r] == X)
cnt_X++;
if (subseq[r] == Y)
cnt_Y++;
}
else
{
ans += subseq.size() - r;
if (subseq[l] == X)
cnt_X--;
if (subseq[l] == Y)
cnt_Y--;
l++;
}
}
}
else
{
i++;
}
}
cout << ans << endl;
return 0;
}