#include <bits/stdc++.h>
using namespace std;
struct RECT {
long long int h, w, num;
} a[100005];
long long int mod = 1e9 + 7, dd[100005], c[100005], p[100005], s[100005], f[100005], h = 0;
bool cmp(RECT aa, RECT bb) {
return aa.h > bb.h;
}
int Find(int x) {
if (x == p[x]) return x;
return p[x] = Find(p[x]);
}
void Merge(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (s[x] > s[y]) swap(x, y);
p[x] = y;
s[y] += s[x]; h += c[x] * c[y];
c[y] += c[x];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].h;
p[i] = i; s[i] = 1;
}
for (int i = 1; i <= n; i++) {
cin >> a[i].w;
a[i].num = i; c[i] = a[i].w;
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
int k = a[i].num;
h += a[i].w * (a[i].w + 1) / 2;
if (dd[k + 1] == 1) {
Merge(k, k + 1);
}
if (dd[k - 1] == 1) {
Merge(k, k - 1);
}
dd[k] = 1;
h %= mod;
f[i] = h;
}
long long int res = 0;
for (int i = 1; i <= n; i++) {
long long int d = a[i].h * (a[i].h + 1) / 2 - a[i + 1].h * (a[i + 1].h + 1) / 2;
d %= mod;
res = (res + d * f[i]) % mod;
}
cout << res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |