This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define N 200005
using namespace std;
typedef long long ll;
ll wth[N], hgt[N], ans;
int p[N];
const int MOD = 1e9+7, DIV = (1e9+8)/2;
int get(int a) {
if(p[a] != a) p[a]=get(p[a]);
return p[a];
}
void join(int a, int b) {
a = get(a); b = get(b);
if(a == b) return;
if(hgt[a] < hgt[b]) swap(a,b);
ans += (1+wth[a])*(wth[a])%MOD*DIV%MOD*(hgt[a]+hgt[b]+1)%MOD*(hgt[a]-hgt[b])%MOD*DIV%MOD;
ans %= MOD;
wth[a] += wth[b];
wth[a] %= MOD;
hgt[a] = hgt[b];
p[b] = a;
}
int H[N], W[N], order[N], n;
bool comp(int a, int b) {
if(H[a] == H[b]) {
return a > b;
}
return H[a] < H[b];
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i ++) {
cin >> H[i];
}
for(int i = 1; i <= n; i ++) {
cin >> W[i];
wth[i] = W[i];
hgt[i] = H[i];
order[i] = i;
p[i] = i;
}
sort(order+1, order+1+n);
for(int j = 1; j <= n; j ++) {
int i = order[j];
if(i-1 && comp(i-1, i)) {
join(i,i-1);
}
if(i+1<=n && comp(i,i+1)) {
join(i,i+1);
}
}
join(0,1);
// int i = get(1);
// ans += wth[i]*hgt[i]%MOD*(wth[i]+1)%MOD*(hgt[i]+1)%MOD*DIV%MOD*DIV%MOD;
// ans %= MOD;
if(ans < 0) ans += MOD;
cout << ans;
}
# | 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... |