| # |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
| 169065922 |
Practice:
rlc202204 |
689D
- 33
|
C++20 (GCC 11-64)
|
Accepted
|
545 ms
|
49304 KB
|
2022-08-20 13:16:37 |
2022-08-20 13:16:37 |
|
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXN_LOG = 30;
int n, a[MAXN] = {0}, b[MAXN] = {0};
int st_mx[MAXN][MAXN_LOG]= {0}, st_mn[MAXN][MAXN_LOG] = {{0}}, pw[MAXN_LOG] = {0}, logN[MAXN] = {0};
void init() {
logN[1] = 0;
for (int i = 2; i <= n; i++)
logN[i] = logN[i / 2] + 1;
for (int i = 0; i <= 20; i++)
pw[i] = (1 << i);
for (int i = 1; i <= n; i++)
st_mn[i][0] = b[i], st_mx[i][0] = a[i];
for (int j = 1; pw[j] <= n; j++)
for (int i = 1; i + pw[j] - 1 <= n; i++) {
st_mx[i][j] = max(st_mx[i][j - 1], st_mx[i + pw[j - 1]][j - 1]);
st_mn[i][j] = min(st_mn[i][j - 1], st_mn[i + pw[j - 1]][j - 1]);
}
}
int QryMax(int l, int r) {
int k = logN[r - l + 1];
return max(st_mx[l][k], st_mx[r - pw[k] + 1][k]);
}
int QryMin(int l, int r) {
int k = logN[r - l + 1];
return min(st_mn[l][k], st_mn[r - pw[k] + 1][k]);
}
int QryDif(int l, int r) {
return QryMax(l, r) - QryMin(l, r);
}
int cal(int x) {
int ll, rr;
int l = x - 1, r = n;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (QryDif(x, mid) >= 0)
r = mid;
else
l = mid;
}
ll = r;
l = x, r = n + 1;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (QryDif(x, mid) > 0)
r = mid;
else
l = mid;
}
rr = l;
return (QryDif(x, ll) == 0 && QryDif(x, rr) == 0 ? rr - ll + 1 : 0);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
init();
long long ans = 0;
for (int i = 1; i <= n; i++)
ans += cal(i);
printf("%lld\n", ans);
return 0;
}
Click to see test details